Submit　　Ranklist

Problem : 177 - 地理報告

Problem Statistics

Solved Member: 23　　Submission: 49　　User Tried: 24

Statement:

天殺的我地理報告還沒碰！

為了完成地理報告，你造訪了很多屬於「樹枝狀水系」的地區

這裡樹枝狀水系的意思是
每個上游地段只會對應地流到一個下游地段、而一個下游地段可能匯集了多個上游地段的水流
簡單來說，河流的各個「觀測點」連起來以後，會變成一個樹狀結構，而樹根就是河流最後的出海口

你走過千山萬水、跋山涉水、君子之交淡如水地取得了各觀測點之間的水流量
也就是樹狀結構上的邊權重
現在你的地理老師想知道，對一個特定的觀測點，它往下游k個點之間的流量總和是多少

Input:Output:

每個測試檔僅有一筆測試資料。
第一行有兩個正整數n,m，以空格隔開(n,m不超過100000，n≧2)
n代表這個樹枝狀水系有幾個「觀測點」(編號1~n，樹根是編號1)、以及接下來將有m筆詢問
緊接著n-1行，每行有u,v,c三個正整數，表達了這棵樹狀結構的n-1條邊，是點編號u,v連接、流量為c(流量不超過10000)

再接下來m行，每行代表一筆詢問，包含s,k兩個正整數
代表地理老師想要知道「從編號s的節點開始，往樹根的方向走k個點、流量的總和是多少」

測試資料中保証詢問的k總是比相應s點的所在層數來得小
也就是說，輸入不會走過頭。也因此我們不會以樹根1作為詢問的s點。
並且輸入的點編號是合法的、給出樹狀結構的邊也將會正確的連接全部n個點

對於每一筆詢問輸出一行，包含一個正整數，即流量總和

Sample Input:Sample Output:

8 5
1 5 9
5 6 2
5 7 4
5 8 5
2 1 17
3 2 11
4 3 15
6 1
7 2
8 2
2 1
4 2

2
13
14
17
26

Source:

101校內培訓

Problem Setter

lajisongyy_jack1

Testdata:

Test	Time	Memory	Score
0	1000ms	65536kb
1-1	1000ms	65536kb	20
1-2	1000ms	65536kb
2	1000ms	65536kb	20
3	1000ms	65536kb	20
4	1000ms	65536kb	20
5-1	1000ms	65536kb	20
5-2	3000ms	65536kb