題目 2466:
信息學奧賽一本通T1560-樹的統(tǒng)計
時間限制: 2s
內存限制: 192MB 提交: 16 解決: 4
題目描述
原題來自：ZJOI 2008
一樹上有 n 個節(jié)點，編號分別為 1 到 n，每個節(jié)點都有一個權值 w。我們將以下面的形式來要求你對這棵樹完成一些操作：
1、CHANGE u t：把節(jié)點 u 權值改為 t；
2、QMAX u v：詢問點 u 到點 v 路徑上的節(jié)點的最大權值；
3、QSUM u v ：詢問點 u 到點 v 路徑上的節(jié)點的權值和。
注意：從點 u 到點 v 路徑上的節(jié)點包括 u 和 v 本身。
輸入格式
第一行為一個數(shù) n，表示節(jié)點個數(shù)；
接下來 n?1 行，每行兩個整數(shù) a,b，表示節(jié)點 a 與節(jié)點 b 之間有一條邊相連；
接下來 n 行，每行一個整數(shù)，第 i 行的整數(shù) wi 表示節(jié)點 i 的權值；
接下來一行，為一個整數(shù) q ，表示操作總數(shù)；
接下來 q 行，每行一個操作，以 CHANGE u t 或 QMAX u v 或 QSUM u v的形式給出。
輸出格式
對于每個 QMAX 或 QSUM 的操作，每行輸出一個整數(shù)表示要求的結果。
樣例輸入
4
1 2
2 3
4 1
4 2 1 3
12
QMAX 3 4
QMAX 3 3
QMAX 3 2
QMAX 2 3
QSUM 3 4
QSUM 2 1
CHANGE 1 5
QMAX 3 4
CHANGE 3 6
QMAX 3 4
QMAX 2 4
QSUM 3 4
提示
數(shù)據(jù)范圍與提示：
對于 100% 的數(shù)據(jù)，有 1≤n≤3×104,0≤q≤2×105 。中途操作中保證每個節(jié)點的權值 w 在 ?30000 至 30000 之間。