a573. E. 子樹問題 - 旦旦解題農場

內容

給你一顆有根樹，一開始根節點為點$1$

以下有兩種操作：

1.把根節點變成點$x$

2.詢問點$x$的子樹大小

子樹大小指的是以點$x$包括自己及所有子孫節點的節點數量

下面此圖為一顆樹及每個節點的子樹大小

輸入說明

單筆測資

第一行有兩個數字$N、Q (1\le N, Q \le 10^5$)，代表樹有$N$個節點，以及有$Q$筆操作

接下來的$N-1$個行，每行有兩個數字$a_i, b_i$，代表點$a_i$與點$b_i$相連

最後$Q$行，每行兩個數字$op(op \in \{1,2\}), x(1\le x \le N)$

若$op = 1$，則將點$x$設為根節點

若$op = 2$，詢問點$x$的子樹大小

保證每筆測資至少會有一筆操作$2$

subtask1 (24%) $ N,Q \le 10^4$
subtask2 (20%) 每個點最多連兩條邊
subtask3 (56%) 無額外限制

輸出說明

對於每個詢問$op = 2$，輸出點$x$的子樹大小

範例輸入

範例輸出

測資資訊：

記憶體限制： 64 MB
不公開測資點#0 (8%): 3.0s , <1M
不公開測資點#1 (8%): 3.0s , <1M
不公開測資點#2 (8%): 3.0s , <1M
不公開測資點#3 (10%): 3.0s , <10M
不公開測資點#4 (10%): 3.0s , <10M
不公開測資點#5 (14%): 3.0s , <10M
不公開測資點#6 (14%): 3.0s , <10M
不公開測資點#7 (14%): 3.0s , <10M
不公開測資點#8 (14%): 3.0s , <10M

提示：

標籤:

109學年度進階班下學期期末考

出處:

[管理者：

fdhs105285 (jakao)

]

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