//很久沒有引進新的演算法了...先來一個比較常規的吧...
給出一棵有根樹，節點編號1..N，根節點是1號節點，每個節點都有一個權值。
維護以下幾種操作：
1.詢問某兩節點x和y之間的唯一路徑上所有節點的權值之和，含x和y；
2.修改某個節點的權值；
3.修改某個節點的父節點。
第一行一個正整數N(1≤N≤100,000)，表示節點個數。
接下來N行，第i行有兩個整數pi和wi，表示節點i的父節點和節點i的權值。特別的，若i=1則pi=0。
接下來的一行又一個正整數Q(1≤Q≤100,000)，表示維護的操作個數。
接下來Q行，每行三個整數t，x和y。
第一個數字t表示操作的類型(1、2或3)。
若t=1，則表示詢問節點x和節點y之間的唯一路徑上所有節點的權值之和；
若t=2，則表示把節點x的權值修改為y；
若t=3，則表示把節點x的父節點修改為節點y，當然x≠1，保證操作后仍然是一棵樹；
保證操作合法。
保證任意時刻任意節點的權值為非負整數且不超過一萬。
對於每個t=1的詢問輸出答案。
5 0 1 1 2 1 3 2 4 2 5 5 1 3 5 2 1 2 1 3 5 3 2 3 1 3 5
11 12 10
| 編號 | 身分 | 題目 | 主題 | 人氣 | 發表日期 |
|
沒有發現任何「解題報告」
|
|||||