q917. 波浪舞 - 高中生程式解題系統

內容

大黑哥最近參加宿營，總召要求大家跳波浪舞，總共有 $n$ 個人，一開始所有人都蹲下，從指定的人開始站起來，每個人看到前面的人站起來就要跟著站起來。
為了快速找到自己的位置，每個人會被編號，並且給每個人正前方唯一指定一個人，只有總召前面沒有人且總召的編號是 1。
因為大黑哥膝蓋痛，被指派了記錄的工作，但因為人數眾多，大黑哥只來得及紀錄每段波浪開始的人是誰及要跳幾次，他希望你幫他計算每個人站起來幾次。

總共有 $q$ 筆紀錄，每筆紀錄有以下兩種
$1\space u \space k$ 代表從 $u$ 開頭跳了 $k$ 次波浪舞
$2\space u$ 代表大黑哥需要你幫他算 $u$ 當下跳了幾次波浪舞並填入

輸入說明

第一行有兩個整數 $n,q$ ，代表有 $n$ 個人，$q$ 筆操作
接下來有 $n-1$ 行，每行有兩個整數 $u,v$ ，代表 $v$ 站在 $u$ 後面
最後有 $q$ 行，每行有以下兩種可能
$1\space u \space k$ 代表從 $u$ 開始跳 $k$ 次波浪舞
$2\space u$ 代表大黑哥想知道 $u$ 當下跳了幾次波浪舞

輸出說明

對於每個詢問 $2\space u$ 輸出一個整數，代表 $u$ 當下跳了幾次波浪舞

範例輸入 #1

範例輸出 #1

8
17
8

測資資訊：

記憶體限制： 64 MB
不公開測資點#0 (5%): 0.5s , <10M
不公開測資點#1 (5%): 0.5s , <10M
不公開測資點#2 (5%): 0.5s , <10M
不公開測資點#3 (5%): 0.5s , <10M
不公開測資點#4 (5%): 0.5s , <10M
不公開測資點#5 (5%): 0.5s , <10M
不公開測資點#6 (5%): 0.5s , <10M
不公開測資點#7 (5%): 0.5s , <10M
不公開測資點#8 (5%): 0.5s , <10M
不公開測資點#9 (5%): 0.5s , <10M
不公開測資點#10 (5%): 0.5s , <10M
不公開測資點#11 (5%): 0.5s , <10M
不公開測資點#12 (5%): 0.5s , <10M
不公開測資點#13 (5%): 0.5s , <10M
不公開測資點#14 (5%): 0.5s , <10M
不公開測資點#15 (5%): 0.5s , <10M
不公開測資點#16 (5%): 0.5s , <10M
不公開測資點#17 (5%): 0.5s , <10M
不公開測資點#18 (5%): 0.5s , <10M
不公開測資點#19 (5%): 0.5s , <10M

提示：

$1 \le u \le n \le 2*10^5$
$1 \le q \le 2*10^5$
$1 \le k \le 10^9$

如果一直吃RE的話可以考慮 stack overflow 的可能性

標籤:

出處:

[管理者： CGSH (快加油吧~~) ]

編號	身分	題目	主題	人氣	發表日期
沒有發現任何「解題報告」