本題為 Two Steps 題，限用 C++ 作答。你可以在這裡找到範例實作以及範例評分程式，詳細注意事項以及常見問題請參考 Hints。
為配合 TIOJ 格式，本題與 YTP 中使用的格式有些不同。

YTP 團隊正在管理一個擁有 $N$ 台伺服器的樹狀網路拓樸（這棵樹是一個二元樹：以主節點為根時，每個節點最多有 $2$ 個子節點），其中有一台最重要的「主節點（Root）」。小 Y 想把這棵樹的拓樸結構備份到另一個資料中心，但負責搞破壞的小 P 會在傳輸過程中把所有伺服器的編號打亂，讓小 Y 無法直接靠編號認出原本的主節點。

小 Y 必須想辦法把原本的主節點給找出來。

這是一題「通訊互動題」（Communication Problem），而且是其中比較特別的一種。 和一般「自己讀 stdin、算完印到 stdout」的題目不同，互動題裡你不直接處理輸入輸出：你只需要實作題目指定的函式，評測系統會提供它自己的一支程式（grader），在編譯時和你的程式合在一起，並在執行時主動呼叫你的函式、透過參數把資料交給你、再接收你的回傳值。整個互動流程由評測系統掌控，你只要把函式寫對即可。

它的特別之處在於分成兩個階段（Phase 1、Phase 2），你要各實作一個函式。最關鍵的限制是：正式評測時，這兩個階段是兩支完全獨立執行的程式（process），彼此不共享任何全域變數或記憶體狀態——你在 Phase 1 對某個全域變數做的修改，到了 Phase 2 完全不會保留。唯一能從 Phase 1「帶到」Phase 2 的資訊，就是你在 Phase 1 回傳、並由系統一路保存下來的那份顏色標籤。這也正是本題的核心：你必須用顏色把「哪個是主節點」的資訊編碼進去，好讓 Phase 2 在節點編號被完全打亂之後，仍然能夠解讀出主節點是誰。

Phase 1

在第一階段，你會得到這棵樹的完整結構，以及主節點的確切編號 $R$（節點編號從 $1$ 到 $N$）。你可以為樹上的每一個節點指派一個「顏色標籤」，顏色的可用選項只有 $0, 1, 2$ 三種。

為了防止標記過於單一，系統規定：對於任何一種顏色 $c \in {0,1,2}$，被塗成該顏色的節點總數，必須大於或等於 $\lfloor N/D \rfloor$（其中 $D$ 會依子任務而不同：子任務一為 $7$、子任務二為 $3$，詳見下方「子任務」一節）。若你的著色方案違反此規定，將會直接獲得 Wrong Answer。

在你完成著色後，請將 $N$ 個節點的顏色透過陣列回傳給系統。

收到你的著色陣列後，系統會將這棵樹的所有節點編號完全隨機打亂（生成一個 $1$ 到 $N$ 的均勻隨機排列）。樹的實體連線結構與每個節點對應的顏色會被完美保留，但你將完全失去原本的節點編號。此外，Phase 2 收到的邊的排列順序、以及每條邊兩個端點的先後順序，也都會被重新隨機打亂，不攜帶任何額外資訊——你只能依靠樹的連線結構與節點上的顏色來判斷主節點。

Phase 2

在第二階段，你會接收到那棵被打亂編號、但帶有你標註顏色的新樹。請根據新樹的連線狀態與節點上的顏色（$0, 1,$ 或 $2$），找出在這棵新樹中，哪一個節點才是原本真正的「主節點」，並回傳其新的節點編號。

子任務

本題有兩個計分子任務，差別在於 Phase 1 著色的「顏色平衡」要求鬆緊不同（對應範例輸入首行的 D）：

• 子任務一（$8$ 分）：每種顏色至少要用在 $\lfloor N/7 \rfloor$ 個節點上（$D = 7$）。
• 子任務二（$12$ 分）：每種顏色至少要用在 $\lfloor N/3 \rfloor$ 個節點上（$D = 3$），限制更嚴格。

每個子任務都是全對才給分：必須該子任務內的所有測試資料都回傳正確的主節點，才能拿到該子任務的分數。

本機測試與提交說明

本題接受 C/C++、Python、Java 三種語言。因為這題需要實作「兩個獨立函式」，跟一般讀 stdin、寫 stdout 的題目不太一樣，所以請務必先閱讀這一段，並下載題目附帶的範本套件（public/ 資料夾）。

範例輸入檔案的第一行格式為 N R D，其中 D 是這筆測資的塗色限制參數（7 代表子任務一的 $\lfloor N/7 \rfloor$，3 代表子任務二的 $\lfloor N/3 \rfloor$）。D 由評測系統使用，不會傳遞給你實作的函式。

不論用哪種語言，你都只需要繳交一個檔案，裡面實作以下兩個函式（下面用 C++ 的型別寫，Python/Java 的對應寫法在各自的範本檔案裡）：

// Phase 1：給定樹的結構 (N 個節點、邊陣列 u, v) 與主節點編號 R，回傳長度為 N 的顏色陣列
// （colors[i] 對應到編號 (i+1) 的節點；顏色只能是 0, 1, 2）
std::vector<int> assign_colors(int n, int r, std::vector<int> u, std::vector<int> v);

// Phase 2：給定「打亂編號後」的樹結構與顏色陣列，回傳你認為的新主節點編號
int find_root(int n, std::vector<int> u, std::vector<int> v, std::vector<int> colors);

以下為 YTP 原題敘，請注意 TIOJ 上無法繳交 Python 與 Java。

C / C++

繳交檔名為 root.cpp，開頭 #include "lib1513.h"。lib1513.h 已經在範本裡，裡面宣告了上面兩個函式，不用自己寫。

本機測試在 public/cpp/ 資料夾下操作：把 root.cpp 換成你的實作，執行 bash compile_cpp.sh 編譯，產生執行檔 root，然後：

./root < ../examples/01.in

本機的 grader 會在同一個 process 裡先跑 Phase 1 再跑 Phase 2，方便 debug。注意：正式評測兩個階段是完全獨立的程式，全域變數不會在兩階段之間保留。

Python

繳交檔名為 root.py，直接在裡面定義 assign_colors(n, r, u, v) 和 find_root(n, u, v, colors) 兩個函式，不需要額外 import。

本機測試把 root.py 放進 public/py/（覆蓋原本的範本檔），然後：

python3 grader.py < ../examples/01.in

Java

繳交檔名為 root.java，需要有 public class root，並在裡面定義兩個非 static 的方法：int[] assign_colors(int n, int r, int[] u, int[] v) 和 int find_root(int n, int[] u, int[] v, int[] colors)。

本機測試在 public/java/ 下，把 root.java 換成你的實作後：

bash compile_java.sh
bash run_java.sh < ../examples/01.in

本機測試程式的輸出

執行本機測試程式後，它會印出一行 test: <結果>：

• test: ok：你的實作在這筆範例上通過了——著色合法（陣列大小為 $N$、每個顏色都是 $0/1/2$、且滿足顏色平衡限制），而且 find_root 正確找出了主節點。
• 否則會印出 test: <失敗原因>，可能的原因包含：assign_colors 回傳的陣列大小不是 $N$、顏色不是 $0/1/2$、違反顏色平衡限制、find_root 回傳的編號超出 $[1, N]$、或找錯了主節點。

這只是 public/ 資料夾中「範例評測程式（sample grader）」的輸出，純粹用來方便你在本機除錯。正式評測使用的是另一套評測程式，其判定方式與輸出格式和這裡完全無關；你的程式本身也不需要、也不應該印出 test: ... 這類文字（你只要把那兩個函式寫對即可）。