1712 . Tentacle Tree
TopCoder
Tags
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 1
4
3 3 3 3
1 2 1
2 3 2
3 4 4
3 3 3 3
1 2 1
2 3 2
3 4 4
Sample Output 1
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 |