TopCoder

User's AC Ratio

87.5% (7/8)

Submission's AC Ratio

47.2% (34/72)

Description

有玩過TENTACLE WAR嗎?
是否還記得當你將三隻細胞的觸手拉成環,自肥時的情景?

現在由於遊戲作者發現拉成環這種做法真是太作弊了!
所以遊戲被作了修正,現在你的觸手最多只能形成一棵樹了!
且每條觸手都是有方向的,都是從深度淺的一端指向深度深的一端。
然而修正之後作者發現遊戲變得太難玩,
所以就加了條件:細胞所傳送的能量是能夠遞移的!
每個細胞的都會有一個遞移常數k,
代表他所傳輸的能量能夠被傳遞k 的距離而不消失,
且其中他所經過的所有細胞都會受到這股能量的補助。

這款修正版遊戲已經要釋出了,
但遊戲作者不知道是否依然會太難玩,便請來了阿ˋ丘來測試遊戲。
身為一隻樹朋友,阿ˋ丘自然希望能夠玩出佳績,
為此,他希望能隨時掌握他觸手樹上哪些細胞受到最多的補助。

現在阿ˋ丘已經把他所拉出的觸手樹的樣子給你了,
你能夠幫他計算出哪些細胞受到最多的補助嗎?

Input Format

對 40% 的測資 1 ≤ n ≤ 3,000
對 100% 的測資 1 ≤ n ≤ 200,000
保證觸手樹上的最長鍊長度≤109

第一行有一個數字n 代表觸手樹上有n 個細胞
第二行有n 個數字,分別代表編號1~n 的細胞的遞移常數。
接下來有 n-1 行,每行有三個數字s , e , l
代表細胞s 向 e伸出了一隻觸手,且這隻觸手長l

Output Format

請輸出一行,代表受到最多補助的細胞是哪些。
請依照編號大小順序輸出,且每兩個細胞間以空格分開。

Sample Input

4
3 3 3 3
1 2 1
2 3 2
3 4 4

Sample Output

3

Hints


1 -> 2 --> 3 ----> 4

  [         ]

       [     ]

             [ ]

Problem Source

原TIOJ1712 / 建國中學99年校內培訓contest #9 prob 5
problem setter:worm

Subtasks

No. Testdata Range Score
1 0 10
2 1 10
3 2 10
4 3 10
5 4 10
6 5 10
7 6 10
8 7 10
9 8 10
10 9 10

Testdata and Limits

No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB) Subtasks
0 8000 65536 262144 1
1 8000 65536 262144 2
2 8000 65536 262144 3
3 8000 65536 262144 4
4 8000 65536 262144 5
5 8000 65536 262144 6
6 8000 65536 262144 7
7 8000 65536 262144 8
8 8000 65536 262144 9
9 8000 65536 262144 10