TopCoder

Caido
$\text{W}ai\text{M}ai\text{QQ}\sim$

User's AC Ratio

97.0% (32/33)

Submission's AC Ratio

54.9% (39/71)

Tags

Description

凱凱最喜歡野外考察了!這個暑假他到各個地方上山下海,一下曬傷一下浮潛,最終苦盡甘來,為台灣帶回了一面地球科學奧林匹亞前半金。雖然地奧閉幕式的直播畫面在凱凱舉起台灣國旗的瞬間就切掉了,但沒有關係,因為我們的凱凱是最棒的。

有一天,凱凱拿到一張野外的地圖,上面有$n$個地點,編號$1 \sim n$,每一個地點都只有一種礦物,而這張地圖是一個二元樹。凱凱一開始在地點$1$,同時也是這棵二元樹的根。凱凱想要走過這張地圖上的所有地點,並且收集每個地方特別的礦物,所以凱凱準備了三個由左到右有$n$格的藏寶匣,想要分別以這棵二元樹的前序遍歷、中序遍歷、後序遍歷的順序,放入各地的礦物。

但長度$n$的藏寶匣實在是太長了,因此凱凱想要把他對折,比較方便攜帶。對折後,第$1$格和第$n$格會變成一格,第$2$格和第$n-1$格會變成一格,以此類推。但問題是,如果這兩格的礦物不一樣,有些性質特殊的碰到可能就會爆炸,這樣可就不好了!(補充:就算他長度是奇數,藏寶匣一樣可以對折就是了)

身為造世主的你,可以決定每個地方要有何種礦物。而你希望能幫這位天才少年一把,因此你要讓對折之後不會有兩種不同礦物碰到的情況。但你又覺得,如果這個世界每個地方都只有同一種礦物,實在是太無聊了,因此你要使礦物種類最多。

此時,你陸陸續續發現有些地方的地形特徵實在是非常接近,沒道理這兩個地方的礦物是不同的,因此你決定讓這兩個地方的礦物是同一種。

總的來說,你會有一棵二元樹,然後請你輸出最多能有幾種不同的礦物。接下來,總共有$q$次發現,第$i$次會有兩個地點$u_i、v_i$,表示$u_i、v_i$兩地的礦物必須相同。然後在每次輸入後,滿足第$1 \sim i$次所有發現的條件下,輸出最多能有幾種礦物。

Input Format

第一行會有兩個整數$n,q$。
接下來第$2 \sim n$行,第$i$行會有兩個數字$p,t$,代表$p$為$i$的父節點,而$t=0$代表$i$為$p$的左子節點、$t=1$則代表$i$為$p$的右子節點。
接著第$n+1 \sim n+q$行,每行會有兩個整數$u,v$,意義如題目中所述。

對於所有測資,都有 $1 \leq n,q \leq 10 ^ 6$

Output Format

第一行請輸出一個數值,表示目前最多相異值的數量。
接下來請輸出$q$行,代表每次發現後的最多相異值數量。

Sample Input

// Sample input 1
5 2
1 0
1 1
2 0
3 1
1 1
1 3

// Sample input 2
10 0
1 0
1 1
2 0
3 0
3 1
2 1
5 0
4 0
6 1

Sample Output

// Sample output 1
2
2
1

// Sample output 2
1

Hints

(如果你知道什麼是二元樹及前中後序遍歷,你可以安全地跳過這段)
二元樹的定義是每個節點至多有兩個子節點,分別為左子節點、右子節點,兩者皆可為空。
而在二元樹上的遍歷通常是使用深度優先搜尋,而我們在描述一個遍歷,或是說將一棵樹變成一個序列時,通常分為三種:
前序:走到一個節點時,先將當前節點加入序列,再將左子樹加入序列,最後將右子樹加入序列。
中序:走到一個節點時,先將左子樹加入序列,再將當前節點加入序列,最後將右子樹加入序列。
後序:走到一個節點時,先將左子樹加入序列,再將右子樹加入序列,最後將當前節點加入序列。
遞迴處理後,可以得到一棵樹的前中後序遍歷。
以下面這棵樹為例。

前序遍歷為:$[1,2,4,9,7,3,5,8,6,10]$
中序遍歷為:$[9,4,2,7,1,8,5,3,6,10]$
後序遍歷為:$[9,4,7,2,8,5,10,6,3,1]$

由於本題輸入量較大,建議使用 scanf/printf 或是使用 cin/cout並在程式前面加上 ios_base::sync_with_stdio(0);cin.tie(0);以加快輸入的速度。
另外,建議在輸出時使用 \n 而非 endl

Problem Source

Subtasks

No. Testdata Range Constraints Score
1 0~1 範例測資 0
2 2~6 $n \leq 1000, q = 0$ 10
3 2~13 $q = 0$ 15
4 2~6, 14~20 $n, q \leq 1000$ 15
5 2~27 無其他限制 60

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 2000 262144 65536 1
1 2000 262144 65536 1
2 2000 262144 65536 2 3 4 5
3 2000 262144 65536 2 3 4 5
4 2000 262144 65536 2 3 4 5
5 2000 262144 65536 2 3 4 5
6 2000 262144 65536 2 3 4 5
7 2000 262144 65536 3 5
8 2000 262144 65536 3 5
9 2000 262144 65536 3 5
10 2000 262144 65536 3 5
11 2000 262144 65536 3 5
12 2000 262144 65536 3 5
13 2000 262144 65536 3 5
14 2000 262144 65536 4 5
15 2000 262144 65536 4 5
16 2000 262144 65536 4 5
17 2000 262144 65536 4 5
18 2000 262144 65536 4 5
19 2000 262144 65536 4 5
20 2000 262144 65536 4 5
21 2000 262144 65536 5
22 2000 262144 65536 5
23 2000 262144 65536 5
24 2000 262144 65536 5
25 2000 262144 65536 5
26 2000 262144 65536 5
27 2000 262144 65536 5