contents
Description
Background
某 M 正與學姊討論蘿莉控追小海女的故事。
某 M 喃喃自語 …
『用了暴力法來完成的話，就能在調整 O(1) - O(E[x]) 完成。』
『如果用一個最常見的樹鏈剖分來完成也不過是 O(log n) - O(log^2 n)』
『在一般情況下，詢問次數肯定比調整次數來得高，想一想常數還得加上去，完全贏不了啊。』
學姊在一旁說到
『那如果是單純的二元樹，有比較好做嗎？說不定有更簡化的算法來完成？』
『說不定那個 … bitvertor 還是 bitset 能完成呢。』
『這個想法難不成是找到 lowbit 嗎？我沒有暫時想法。』某 M 這麼回答道。
『也許吧 … 我也不確定』學姊簇著眉。
某 M 發了瘋似的想了一個算法
『如果我們將其轉換成 k-ary search tree，也就是說需要將節點編號重新編成有大小關係，然後維護一個 BST 來查找 lower_bound 的結果，這麼一來就是 O(k log n) - O(log n) 了！』
『啊啊啊，這個方法不可行，』
學姊將鄙視般的眼神投向某 M。看來這場病還要持續很久。
『將題目弄成找樹前綴和好了，既然暴力法有期望值的剪枝，讓它剪不了不就好了！』
『你覺得不會被其他解法坑殺嗎 …』學姊如此擔憂地表示到。
『沒關係，吾等 M 可不是說假的』
Problem
給定一棵樹，樹根 root 編號 0，每個點一開始的權重為 0。
操作 x k: 將節點 x 的權重增加 k，請輸出從 x 到 root 的權重和。
Input
輸入有多組測資，每組測資第一行會有一個整數 N (N < 32767)，表示這棵樹有多少個節點。
接下來會有 N - 1 行，每一行上會有兩個整數 u, v (0 <= u, v < N) 表示 u, v 之間有一條邊。
接下來會有一行上有一個整數 Q (Q < 32767)，表示接下來有 M 組詢問。
Output
對於每個詢問結果輸出一行，請參照範例輸出的說明。
每組測資後空一行。
Sample Input
|
|
Sample Output
|
|
More
名為 “學姊”。
Solution
|