凱凱最喜歡野外考察了!這個暑假他到各個地方上山下海,一下曬傷一下浮潛,最終苦盡甘來,為台灣帶回了一面地球科學奧林匹亞前半金。雖然地奧閉幕式的直播畫面在凱凱舉起台灣國旗的瞬間就切掉了,但沒有關係,因為我們的凱凱是最棒的。
有一天,凱凱拿到一張野外的地圖,上面有
但長度
身為造世主的你,可以決定每個地方要有何種礦物。而你希望能幫這位天才少年一把,因此你要讓對折之後不會有兩種不同礦物碰到的情況。但你又覺得,如果這個世界每個地方都只有同一種礦物,實在是太無聊了,因此你要使礦物種類最多。
此時,你陸陸續續發現有些地方的地形特徵實在是非常接近,沒道理這兩個地方的礦物是不同的,因此你決定讓這兩個地方的礦物是同一種。
總的來說,你會有一棵二元樹,然後請你輸出最多能有幾種不同的礦物。接下來,總共有
第一行會有兩個整數
接下來第
接著第
對於所有測資,都有
第一行請輸出一個數值,表示目前最多相異值的數量。
接下來請輸出
(如果你知道什麼是二元樹及前中後序遍歷,你可以安全地跳過這段)
二元樹的定義是每個節點至多有兩個子節點,分別為左子節點、右子節點,兩者皆可為空。
而在二元樹上的遍歷通常是使用深度優先搜尋,而我們在描述一個遍歷,或是說將一棵樹變成一個序列時,通常分為三種:
前序:走到一個節點時,先將當前節點加入序列,再將左子樹加入序列,最後將右子樹加入序列。
中序:走到一個節點時,先將左子樹加入序列,再將當前節點加入序列,最後將右子樹加入序列。
後序:走到一個節點時,先將左子樹加入序列,再將右子樹加入序列,最後將當前節點加入序列。
遞迴處理後,可以得到一棵樹的前中後序遍歷。
以下面這棵樹為例。
前序遍歷為:
中序遍歷為:
後序遍歷為:
由於本題輸入量較大,建議使用 scanf/printf
或是使用 cin/cout
並在程式前面加上 ios_base::sync_with_stdio(0);cin.tie(0);
以加快輸入的速度。
另外,建議在輸出時使用 \n
而非 endl
。
No. | Testdata Range | Constraints | Score |
---|---|---|---|
1 | 0~1 | 範例測資 | 0 |
2 | 2~6 | 10 | |
3 | 2~13 | 15 | |
4 | 2~6, 14~20 | 15 | |
5 | 2~27 | 無其他限制 | 60 |