1447 . 巴乙己公司問題
TopCoder
Tags
Description
巴乙己開了一間公司，隨著日子一天一天過去，巴乙己公司的業績也蒸蒸日上，身為好老闆的巴乙己，決定要為員工們加薪。
巴乙己公司裡有 $N$ 名員工，每個員工都擁有自己的員工編號，員工編號是流水號，最早入職的員工的編號就是 $1$，而最晚入職的員工編號則是 $N$。因為巴乙己公司暫時還不開放離職，所以不用擔心空號的問題。
除了公司的 CEO 以外，每個員工 $i$ 都有一個直屬上司 $p_i$，並且我們說 $i$ 是 $p_i$ 的直屬下屬。這家公司不存在「老闆環」的關係，也就是不存在一些員工 $x_1,x_2,\dots,x_k$ 使得對於 $1 \leq i < k$，滿足 $p_{x_i}=x_{i+1}$，且$p_{x_k}=x_1$。一個員工 $i$ 所帶領的團隊，包含他自己、他的直屬下屬，以及他的任何一個直屬下屬所帶領的團隊成員。
因為巴乙己公司講究個人實力，當然有可能一個員工的上司是一個比他還晚入職的員工，大多數人都對此沒什麼意見。不過，在跟薪水有關的事情上面就不一定了，一個人要是發現另一個比他晚入職的同事，領有比他更高的薪水，那他可能就會有點不開心。為了避免員工不開心，但又要好好獎勵有貢獻的員工，巴乙己在為員工們加薪的同時，也要好好掌握這種狀況的嚴重程度。
在開始進行本次的加薪之前，每個員工的薪水都是一樣多的。接下來有 $Q$ 個事件，事件分成兩種：
- $1\ x\ v$：巴乙己幫第 $x$ 個員工加薪 $v$ 元。注意巴乙己可能也會幫不乖的員工扣薪，扣薪也算是一種加薪，如果 $v<0$，就代表這名員工被扣薪了。也有可能 $v=0$，代表這筆記錄是巴乙己加爽的，實際上對員工的薪水沒有影響。
- $2\ x\ t$：巴乙己想知道在員工 $x$ 所帶領的團隊中，編號 $\leq t$ 的所有員工目前為止的加薪總和。
請幫巴乙己算出所有第二種事件的答案。
Input Format
第一行有兩個整數 $N,Q$，代表員工的人數與事件數量。
第二行有 $N$ 個數字 $p_1,p_2,\dots,p_N$，代表員工 $i$ 的直屬上司是 $p_i$，若員工 $i$ 是 CEO，則 $p_i=-1$。
接下來有 $Q$ 行，其中第 $i$ 行代表第 $i$ 個事件的資訊，格式為以下其中之一：
- $1\ x\ v$：員工 $x$ 被加薪了 $v$ 元。
- $2\ x\ t$：巴乙己想知道員工 $x$ 帶領的團隊中，編號 $\leq t$ 的員工目前為止的加薪總和。
- $1 \leq N,Q \leq 3 \times 10^ 5$
- $1 \leq p_i \leq N$ 或 $p_i=-1$
- $1 \leq x \leq N$
- $-10^ 9 \leq v \leq 10^ 9$
- $1 \leq t \leq N$
- 保證不存在一連串的員工 $x_1,x_2,\dots,x_k$ 滿足 $\forall 1 \leq i < k,\ p_{x_i}=x_{i+1}$ 且 $p_{x_k}=x_1$
- 保證恰有一個 $i$ 滿足 $p_i=-1$
Output Format
對於每個第二種事件，輸出一行，包含一個整數，代表該事件的答案。
Sample Input 1
7 5 4 -1 2 2 3 4 3 1 1 10 2 4 2 1 4 100 2 4 2 2 4 4
Sample Output 1
10 10 110
Hints
Problem Source
Subtasks
| No. | Testdata Range | Constraints | Score |
|---|---|---|---|
| 1 | 0 | 範例測資。 | 0 |
| 2 | 0~26 | 無特別限制。 | 100 |