27 . 奇怪的樹上操作

Submit
Status
Discussion / Solution
Ranklist
Back to Problems List

TopCoder

089487

User's AC Ratio

100.0% (53/53)

Submission's AC Ratio

49.8% (154/309)

Tags

ioicamp ioicamp-2024

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≤N≤2×105
  • 1≤Q≤2×105
  • 0≤ci≤106

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

Sample Output 1

7
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

Sample Output 2

2
2
1
1
3
2
0
0
3
1
1
10
6

Hints

Problem Source

IOICamp 2024 Day3 pB

Subtasks

No. Testdata Range Constraints Score
1 0~1 範例測資 0
2 2~22 只有第一種操作與第三種操作 50
3 0~63 無額外限制 50

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 2000 524288 65536 1 3
1 2000 524288 65536 1 3
2 2000 524288 65536 2 3
3 2000 524288 65536 2 3
4 2000 524288 65536 2 3
5 2000 524288 65536 2 3
6 2000 524288 65536 2 3
7 2000 524288 65536 2 3
8 2000 524288 65536 2 3
9 2000 524288 65536 2 3
10 2000 524288 65536 2 3
11 2000 524288 65536 2 3
12 2000 524288 65536 2 3
13 2000 524288 65536 2 3
14 2000 524288 65536 2 3
15 2000 524288 65536 2 3
16 2000 524288 65536 2 3
17 2000 524288 65536 2 3
18 2000 524288 65536 2 3
19 2000 524288 65536 2 3
20 2000 524288 65536 2 3
21 2000 524288 65536 2 3
22 2000 524288 65536 2 3
23 2000 524288 65536 3
24 2000 524288 65536 3
25 2000 524288 65536 3
26 2000 524288 65536 3
27 2000 524288 65536 3
28 2000 524288 65536 3
29 2000 524288 65536 3
30 2000 524288 65536 3
31 2000 524288 65536 3
32 2000 524288 65536 3
33 2000 524288 65536 3
34 2000 524288 65536 3
35 2000 524288 65536 3
36 2000 524288 65536 3
37 2000 524288 65536 3
38 2000 524288 65536 3
39 2000 524288 65536 3
40 2000 524288 65536 3
41 2000 524288 65536 3
42 2000 524288 65536 3
43 2000 524288 65536 3
44 2000 524288 65536 3
45 2000 524288 65536 3
46 2000 524288 65536 3
47 2000 524288 65536 3
48 2000 524288 65536 3
49 2000 524288 65536 3
50 2000 524288 65536 3
51 2000 524288 65536 3
52 2000 524288 65536 3
53 2000 524288 65536 3
54 2000 524288 65536 3
55 2000 524288 65536 3
56 2000 524288 65536 3
57 2000 524288 65536 3
58 2000 524288 65536 3
59 2000 524288 65536 3
60 2000 524288 65536 3
61 2000 524288 65536 3
62 2000 524288 65536 3
63 2000 524288 65536 3
Submit
Back to Top