27 . 奇怪的樹上操作
TopCoder
Tags
Description
給一棵 $N$ 個節點的樹定根在 $1$，一開始每個點點權都是 $0$，接下來共 $Q$ 次操作:
- $1\ u\ c$ 將 $u$ 的點權增加 $c$。
- $2\ u\ v$ 詢問 $u, v$ 路徑的總和。
- $3\ u$ 詢問 $u$ 子樹內的總和。
Input Format
第一行兩個正整數 $N, Q$，代表樹的節點樹以及接下來的詢問次數。
第二行共 $N - 1$ 個正整數，第 $i$ 個表示編號 $i + 1$ 的節點父親是誰。
接下來會有 $Q$ 行詢問，格式如題序。
- $2 \leq N \leq 2 \times 10^ 5$
- $1 \leq Q \leq 2 \times 10^ 5$
- $0 \leq c_i \leq 10^ 6$
Output Format
對於所有第二三種操作輸出一個非負整數。
Sample Input 1
7 5
1 1 2 1 2 1
1 1 5
1 2 2
2 4 1
2 3 5
3 3
1 1 2 1 2 1
1 1 5
1 2 2
2 4 1
2 3 5
3 3
Sample Output 1
7
5
0
5
0
Sample Input 2
10 20
8 8 5 1 5 8 9 6 5
1 1 2
1 2 1
1 5 2
2 3 10
2 10 8
3 9
3 9
2 4 2
2 4 9
3 3
3 7
3 5
3 8
1 5 7
1 9 1
3 8
2 7 10
1 7 4
3 6
1 9 6
8 8 5 1 5 8 9 6 5
1 1 2
1 2 1
1 5 2
2 3 10
2 10 8
3 9
3 9
2 4 2
2 4 9
3 3
3 7
3 5
3 8
1 5 7
1 9 1
3 8
2 7 10
1 7 4
3 6
1 9 6
Sample Output 2
2
2
1
1
3
2
0
0
3
1
1
10
6
2
1
1
3
2
0
0
3
1
1
10
6
Hints
Problem Source
Subtasks
| No. | Testdata Range | Constraints | Score |
|---|---|---|---|
| 1 | 0~1 | 範例測資。 | 0 |
| 2 | 2~22 | 只有第一種操作與第三種操作。 | 50 |
| 3 | 0~63 | 無特別限制。 | 50 |