晨佃是個擁有非常龐大國土的王朝，因此鑒於偏僻蠻荒地帶難以掌握，晨佃王朝發展出一套層層管理的系統，而晨佃王朝的首都是獨立歸屬於第一級別的城市，其他所有的城市都有恰好有一個直屬城市，而每個城市的級別即是其直屬城市級別數加一，簡而言之，若某城市的直屬城市屬於第Ｎ級別，則該城市即為第Ｎ＋１級別，此外，若一個第Ｎ級別的城市，其直接管轄其下的第Ｎ＋１級城市外，亦包含第Ｎ＋１級城市所管轄的城市，以及再往下皆依此類推（因此所有城市都屬於晨佃王朝首都的管轄範圍），當然城市本身也是自己的管轄範圍。然而當晨佃國王將他的城市一一規畫好之後，發現為了讓城市能被其直屬城市直接管轄，都必須建造一條直接相連的路，是的，如同你所想的一樣，每條道路都有不盡相同的建造金額，不過不幸的，晨佃國王秉持著向人民徵最少的稅的宗旨，因此建造完所有的路恐怕會造成民不聊生，所以晨佃國王決定放棄部分的城市，也就是只建造部份的路，此時，你正好身為晨佃國御用程式設計師，你便自告奮勇的決定幫助晨佃國王解決這個難題，因此晨佃國王會先將他的城市規劃以及建造道路的費用交給你，接著你必須回答若干個晨佃國王所提出的問題，也就是城市ａ到城市ｂ所要建造的道路總花費是多少，由於是為了管理而建造，城市ａ必須能管轄城市ｂ，然而國事繁雜晨佃國王有可能提出的問題並非為城市ａ能管轄城市ｂ，此時你便不需要回答，然而這樣會造成你編程的麻煩，所以你決定為自己賺取更多的酬勞，因此在晨佃國王提出不合理的問題後，每條道路建造費用都會提高１單位的花費，當然浮報帳目這件事只有你自己知道。
注：若a=b，則認為不合法。2015/7/15 by liouzhou_101
第一行有一個正整數 n ( n ≦ 2,000,000 )，表示晨佃國的城市數。
接下來第二到第 n 行，每行有兩個正整數 p , c ( c ≦ 10,000 )，
依序表示編號二到編號 n 的城市其直屬城市編號( p )以及建造該條道路的花費( c )。
( 編號 1 即為晨佃王朝首都所在 )
第 n+1 行有一個正整數 q ( q ≦ 100,000 )，表示晨佃國王的詢問數。
接下來 q 行，每行有兩個正整數a , b ( a , b ≦ n )，
表示晨佃國王詢問建造城市 a 到城市 b 的道路總花費。
對於每筆合理的詢問輸出一行，
表示建造該段道路的總花費（當然必須加上你準備浮報的帳目）。
4 1 3 1 7 2 5 3 1 4 2 3 1 4
8 10
對於範例測資：
除了管轄自己城市本身以外，
編號一的城市也就是晨佃首都管轄城市編號二、三、四，
編號二的城市管轄城市編號四，
而編號三及編號四的城市無管轄其他任何城市。
對於晨佃國王第一筆詢問：
需建造城市編號一到二及二到四的道路，總花費為3+5=8。
對於晨佃國王第二筆詢問：
由於城市二並無管轄城市三，所以你決定對每段道路多浮報一單位的花費。
因此加上你準備浮報的道路花費便成為：
1 - 2 : 4
1 - 3 : 8
2 - 4 : 6
對於晨佃國王第三筆詢問：
需建造城市編號一到二及二到四的道路，總花費為4+6=10。
※ 由於測試資料較大，建議使用較快的輸出入。
保證 20% 的測資，n ≦ 10
保證 40% 的測資，n ≦ 1,000
保證 70% 的測資，n ≦ 100,000 , q ≦ 1,000
| 編號 | 身分 | 題目 | 主題 | 人氣 | 發表日期 |
|
沒有發現任何「解題報告」
|
|||||