你的程式需要在一開始使用前置處理器引入 lib0913.h，詳細請參考範例實作。

你需要完成以下的兩個函式：

void Init(int N);

• 在一筆測試資料中，Init 會被呼叫恰 $T$ 次。
• 引數 N 代表這棵樹的節點數量。
• 節點的編號為 $1, 2, \ldots, N$，且為一前序遍歷的結果。

int GetId(int x, std::vector<int> nearby);

• 在一筆測試資料中，GetId 會被呼叫至多 $500\ 000$ 次。
• 呼叫完 Init(N) 後會呼叫恰 $N$ 次 GetId，且保證 $N$ 次傳入的的 x 都不一樣。在這 $N$ 次 GetId 呼叫結束前，不會有任何的 Init 呼叫。
• 引數 x 代表節點的編號，且 $1 \leq x \leq N$。
• 引數 nearby 代表節點 $x$ 的鄰居。
• 回傳值必須為一個介於 $-2^ {31}$ 到 $2^ {31} - 1$ 的整數，代表你要幫編號為 $x$ 的節點賦上的權重。
• 呼叫完一次 Init(N) 與 $N$ 次 GetId 後，評測系統會幫你用題目敘述中描述的方式連邊，你必須要確保連邊後任兩個點的路徑都不能包含超過 $2\lfloor \log_2(N) \rfloor$ 條黑邊。

如果任意一個條件沒有被滿足，你的程式會被判斷為 Wrong Answer 並且獲得 0 分，否則，你的程式將依照 Scoring 中的敘述評分。

• $1 \leq T \leq 5 \times 10^ 5$
• $1 \leq N \leq 5 \times 10^ 5$
• 所有的 $N$ 加起來 $\leq 5 \times 10^ 5$

範例評分程式以下列方式輸入：

• line $1$: $T$ $seed$
• line $2i$: $N$
• line $2i + 1$: $p_2$ $p_3$ $\ldots$ $p_N$

$T$ 代表測試資料的數量，$seed$ 代表範例評分程式用於決定 GetId 詢問順序的偽隨機種子。
請注意範例評分程式中決定 GetId 的方式不一定與實際評分所使用的方法相同。

每一筆測試資料中 $p_i$，代表該樹第 $i$ 個節點的父親為 $p_i$。請注意編號為 $1$-based。範例評分程式會幫你按照前序遍歷重新編號，意即：你傳入的樹編號不需為一前序遍歷的結果。

範例評分程式以下列方式輸出：

如果你的程式被判斷為 Accepted，範例評分程式會輸出 Accepted。

如果你的程式被判斷為 Wrong Answer，範例評分程式會輸出 Wrong answer: i to j passes x black edges, limit = y，其中 $i$ 與 $j$ 為兩個沒符合條件的節點，該兩點之間有 $x$ 條黑邊，而限制為 $y$ 條。

另外請注意，範例評分程式的運行效率較慢，若需要更高速的效率請自行修改。

由於 Windows Defender 以及各種奇怪東西的限制，本題的範例編譯指令不提供 Windows 批次檔。編譯及測試教學請參考下列說明。

• 如果你的系統是 Linux，你可以直接執行 compile.sh 編譯你的程式，編譯結果會是 ordered-tree.exe，請直接用命令列執行該檔案。
• 如果你的系統是 MacOS，你需要將 compile.sh 當中的 -static 參數移除，其餘與 Linux 相同。
• 如果你的系統是 Windows，你有以下的選擇：
  1. 本地測試時加入 #include "grader.cpp"，並且以單一檔案的編譯執行方式測試，請注意這一行上傳時需要刪除，否則你會獲得一個 Compile Error。
  2. 將 compile.sh 的變數替換後直接於命令列執行，請注意你需要確保 g++ 在系統的環境變數 PATH 中。
  3. 如果你的電腦已經有 WSL (Windows Subsystem for Linux)，你可以直接使用 WSL 並按照 Linux 的做法。
  4. 使用電腦教室的 Ubuntu（啟動時可以選擇系統）並按照 Linux 的做法。

IOICamp 2025 Day3 pE