2277 . 礦物採集
TopCoder
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 1
1 0
1 1
2 0
3 1
1 1
1 3
Sample Output 1
2
1
Sample Input 2
1 0
1 1
2 0
3 0
3 1
2 1
5 0
4 0
6 1
Sample Output 2
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 |