這是一道互動題。
題目敘述
給出五元組 $(T,I,S_V,S_E,\iota)$，其中：
- $T$ 是一棵 $n$ 個點的有根樹 $T=(V,E)$，其中 $V$ 為 $T$ 的點集，$E$ 為 $T$ 的邊集。樹的節點被編號為 $1,2,\ldots,n$，其中根節點編號為 $1$。
- $I$ 是一個集合，集合中的元素稱作資訊。其中有兩個不同的特殊元素：單位元 $\epsilon$ 和不合法資訊 $\bot$。
對於一般的資訊，其都具有點集合和邊集合兩個屬性。特別地，對於單位元，其只有邊集合的屬性，而對於不合法資訊，其沒有以上兩種屬性。
- 對於資訊 $o\in I\setminus\{\epsilon,\bot\}$，$o$ 的點集合是 $V$ 的一個二元子集，記作 $S_V(o)$，滿足 $S_V(o)\subseteq V$ 且 $|S_V(o)|=2$。其中，兩個集合 $A,B$ 的差 $A\setminus B$ 被定義為 $A\setminus B=\{x\in A\mid x\notin B\}$。
- 對於資訊 $o\in I\setminus\{\bot\}$，$o$ 的邊集合是 $E$ 的一個子集，記作 $S_E(o)$，滿足 $S_E(o)\subseteq E$。規定單位元的邊集合為空，也即 $S_E(\epsilon)=\varnothing$。
- 對於樹上的任何一條邊 $e\in E$，記 $e=(u,v)$，存在一個關於 $e$ 的資訊 $\iota(e)\in I$，它以其端點為點集合、自身為邊集合，即 $S_V(\iota(e))=\{u,v\},S_E(\iota(e))=\{e\}$。
資訊有兩種合併的方式，分別記作 $R$ 和 $C$。對於 $\forall a,b\in I$，記 $r=R(a,b),c=C(a,b)$，滿足 $r,c\in I$，則：
- 單位元和任何資訊合併都得到對方。也即，如果 $a=\epsilon$，那麼 $r=c=b$；如果 $b=\epsilon$，那麼 $r=c=a$。
- 不合法資訊和任何資訊合併都得到不合法資訊。也即，如果 $a=\bot$ 或者 $b=\bot$，那麼 $r=c=\bot$。
- 對於剩下的情況，如果兩個資訊的邊集合的交集非空，或者點集合的交集的大小不為 $1$，則合併得到不合法資訊。也即，如果 $S_E(a)\cap S_E(b)\ne\varnothing$ 或 $|S_V(a)\cap S_V(b)|\ne 1$，則 $r=c=\bot$。
- 否則，有
$$ S_E(r)=S_E(c)=S_E(a)\cup S_E(b), $$
$$ S_V(r)=S_V(a), $$
$$ S_V(c)=S_V(a)\oplus S_V(b). $$
其中 $\oplus$ 表示集合的對稱差運算，也即 $A\oplus B=(A\cup B)\setminus(A\cap B)$。
定義 $T$ 中兩個點的樹上距離為樹上以兩個點為端點的唯一簡單路徑經過的邊數。
給出評分參數 $M$ 和 $q$ 次詢問，每次詢問給出樹上的一個點 $u$ 和一個非負整數 $d$。記點集 $X$ 為 $T$ 中所有與 $u$ 的樹上距離不超過 $d$ 的點構成的集合，又記邊集 $Y=\{(a,b)\in E\mid a,b\in X\}$ 為 $X$ 內部的邊集。可以證明，從 $\epsilon$ 和所有 $\iota(e)\ (e\in E)$ 出發，總是能透過有限次 $R,C$ 的呼叫得到資訊 $o\ne\bot$ 滿足 $S_E(o)=Y$。
每組詢問中，你需要在 $R$ 和 $C$ 的呼叫次數總和不超過 $M$ 的限制下構造出一個滿足這樣的要求的資訊 $o$。特別地，如果 $d=0$，則直接回傳單位元 $\epsilon$ 即可。
實作細節
請確保你的程式開頭有 #include "count.h"。
標頭檔 count.h 中實作了如下內容：
- 定義了資訊對應的資料型別
info； - 定義了 $\epsilon$ 所對應的
info型別常數emptyinfo，你可以在程式中直接使用。 - 定義並實作了以下兩個資訊合併函數，你可以在程式中直接呼叫：
info MR(info a,info b);
info MC(info a,info b);- 兩個函數分別回傳 $R(a,b)$ 與 $C(a,b)$ 對應的資訊。
你需要保證呼叫 $R(a,b)$ 或 $C(a,b)$ 時結果不為 $\bot$，否則程式可能會出現異常行為。
- 定義並實作了判定一個資訊是否為單位元的函數，你可以在程式中直接呼叫：
bool isempty(info a);- 這個函數回傳真若且唯若 $a$ 為單位元。
可以查看參考互動函式庫了解更多實作細節。
你不需要，也不應該實作主函數。你需要實作如下幾個函數：
void init(int T, int n, int q, vector<int> fa, vector<info> e, int M);T表示測試點編號，n表示樹的點數，q表示詢問數，M表示該測試點的評分參數。fa和e的長度均為 $n-1$。對於 $0\le i<n-1$，$fa[i]$ 和 $i+2$ 為第 $i$ 條邊 $e_i$ 的兩個端點，e[i]為題目敘述中提到的 $\iota(e_i)$ 所對應的info型別元素。資料保證 $fa[i]$ 小於 $i+2$。
info ask(int u, int d);- 給出一個詢問，參數的意義見題目敘述。你需要在函數結束時回傳一個滿足題設條件的資訊。
最終測試時，在每個測試點，互動函式庫會恰好呼叫一次 init 函數，隨後呼叫 $q$ 次 ask 函數。互動函式庫會使用特殊的實作方式，單個 info 型別的變數會恆定消耗 12 位元組記憶體，這與下發的參考互動函式庫不同。為保證程式執行時記憶體使用在題目限制內，你需要保證執行過程中沒有過多的 info 型別變數同時存在。
保證在滿足呼叫次數限制且不進行 isempty 函數呼叫的情況下，最終測試的互動函式庫執行所需的時間不超過 0.6 秒，互動函式庫本身所消耗的記憶體不超過 16 MiB。保證在只執行 $10^8$ 次 isempty 函數呼叫的情況下，最終測試的互動函式庫執行的時間不超過 0.25 秒。
在下發檔案中包含一個名為 count.cpp 的檔案，作為範例程式，選手可以在此基礎上繼續實作本題。在下發檔案中還額外包含一個名為 count_backup.h 的備份檔案，我們保證其與 count.h 檔案完全相同。
測試程式方式
本題目錄下提供了兩個互動函式庫的參考實作 grader.o、checker.o，其為兩個不同的互動函式庫編譯產生的可連結檔案。最終測試時所用的互動函式庫實作與該實作有不同，因此選手的解法不應依賴互動函式庫的具體實作，同時也不應該依賴 count.h 中 info 型別的具體實作。
你需要修改下發的 count.h 來幫助進行連結。具體地，在將原始碼 count.cpp 和程式 grader.o 進行連結的時候，你需要註解掉 count.h 程式碼的第 5 行，並保留第 4 行的程式碼。連結 checker.o 方法類似，需要註解掉 count.h 程式碼的第 4 行，並保留第 5 行的程式碼。選手可以對 count.h 的實作自行修改來實現不同程式的編譯。
修改後，選手可以在本題目錄下使用如下命令編譯得到可執行程式：
g++ count.cpp -c -O2 -std=c++14 -lm && g++ count.o grader.o -o count g++ count.cpp -c -O2 -std=c++14 -lm && g++ count.o checker.o -o count
其中第一行命令會編譯目前 count.cpp 後與 grader.o 連結起來，生成可執行檔案 count，第二行命令則會編譯目前 count.cpp 後與 checker.o 連結起來，生成可執行檔案 count。
按上述方法編譯得到的可執行檔案 count，其執行方式如下：
可執行檔案將從標準輸入讀入以下格式的資料：
- 第一行四個整數 $id,n,q,M$，分別表示測試點編號、樹的點數、詢問數和評分參數；
- 第二行 $n-1$ 個整數 $p_2,p_3,\cdots,p_n$，分別表示 $2$ 至 $n$ 的父親節點編號，在本地除錯時你需要保證 $\forall i\in[2,n],p_i<i$；
- 接下來 $q$ 行每行兩個整數 $u,d$，描述一次詢問。
讀入之後，互動函式庫會進行測試。如果你的程式不滿足互動函式庫限制，其會在輸出中回傳對應的錯誤資訊。否則，對於連結的可執行檔案，其輸出如下：
總共一行三個整數 $C_1,C_2,C_3$，其中：
- $C_1$ 表示程式在
init函數中呼叫互動函式庫函數的總次數； - $C_2$ 表示程式在執行過程中呼叫互動函式庫函數的總次數；
- $C_3$ 表示程式在 $q$ 次
ask函數中呼叫互動函式庫函數的次數的最大值。 - 對於上述三個統計量，我們只會計入
MR、MC函數的呼叫次數，而不會計入isempty函數的呼叫次數。
- $C_1$ 表示程式在
在連結不同檔案的時候，其能夠進行的檢查也不同，具體地：
- grader.o：其在執行時不會檢查
ask函數回傳的資訊是否正確，但可以幫助選手判斷互動操作是否符合要求。這份程式執行時間最接近評測時的互動函式庫，因此選手可以利用該程式測試執行速度，但不保證程式正確性。 - checker.o：其在執行時會檢查
ask函數回傳的資訊是否正確，也可以幫助選手判斷互動操作是否符合要求。同時其會檢查ask函數回傳的資訊是否正確。這份程式可以進行答案正確性的檢查。
- grader.o：其在執行時不會檢查
選手在除錯時需要保證輸入可執行檔案 count 的資料滿足上述輸入格式，否則不保證輸出結果正確。
範例
範例 1
見選手目錄下的 count/count1.in 與 count/count1.ans。
範例 2
見選手目錄下的 count/count2.in 與 count/count2.ans。
該組範例滿足資料範圍中的特殊性質 A。
範例 3
見選手目錄下的 count/count3.in 與 count/count3.ans。
該組範例滿足資料範圍中的特殊性質 B。
範例 4
見選手目錄下的 count/count4.in 與 count/count4.ans。
子任務
最終評測只會收取 count.cpp，修改選手目錄下其他檔案不會對評測結果產生影響。注意：
- 未初始化的
info型別的變數不保證是emptyinfo。 - 請不要嘗試存取或修改
info型別的成員變數，否則將被視為攻擊互動函式庫。 - 請不要在
init函數呼叫之前呼叫MR和MC函數，否則可能會發生未定義行為。 - 你只能存取自己定義的變數和互動函式庫回傳的
info型別變數，嘗試存取其他空間將可能導致編譯錯誤或執行時錯誤。
本題首先會受到和傳統題相同的限制，例如編譯錯誤會導致整道題目得 0 分，執行時錯誤、超過時間限制、超過空間限制等會導致相應測試點得 0 分等。
在上述條件以外，在一個測試點中，若程式執行了非法的函數呼叫或詢問操作中給出了錯誤回答，該測試點將會獲得 0 分。否則，記 $C_1,C_3$ 分別表示你的程式在 init 函數中呼叫互動函式庫函數的次數，和你的程式在所有 $q$ 次 ask 函數中呼叫互動函式庫函數的次數的最大值。如果 $C_1\le 3\cdot 10^7$ 且 $C_3$ 不超過該測試點的評分參數 $M$，你將獲得該測試點的分數，否則你無法獲得該測試點的分數。注意：計算 $C_1,C_3$ 時只會計入 MR、MC 函數的呼叫次數，而不會計入 isempty 函數的呼叫次數。
資料範圍
對於所有測試點，$1\le n\le 2\cdot 10^5,1\le q\le 10^6$；每組詢問中，有 $1\le u\le n,1\le d\le n-1$。
| 測試點 | $n=$ | $q=$ | 特殊性質 | $M=$ |
|---|---|---|---|---|
| 1 | $10^3$ | $10^4$ | $500$ | |
| 2 | $2000$ | $10^4$ | $500$ | |
| 3,4 | $10^5$ | $10^6$ | A | $5$ |
| 5,6 | $6\times 10^4$ | $6\times 10^4$ | B | $50$ |
| 7 | $6\times 10^4$ | $6\times 10^4$ | B | $5$ |
| 8 | $10^5$ | $10^5$ | B | $5$ |
| 9 | $7500$ | $5\times 10^4$ | C | $500$ |
| 10 | $10^4$ | $5\times 10^4$ | D | $500$ |
| 11 | $15000$ | $5\times 10^4$ | D | $500$ |
| 12 | $2\times 10^4$ | $5\times 10^4$ | D | $50$ |
| 13 | $25000$ | $5\times 10^4$ | D | $5$ |
| 14 | $3\times 10^4$ | $10^5$ | D | $5$ |
| 15 | $6\times 10^4$ | $10^6$ | D | $5$ |
| 16 | $6\times 10^4$ | $10^6$ | D | $5$ |
| 17 | $8\times 10^4$ | $10^6$ | D | $5$ |
| 18 | $10^5$ | $10^6$ | D | $5$ |
| 19 | $1.5\times 10^5$ | $10^6$ | D | $5$ |
| 20 | $2\times 10^5$ | $10^6$ | D | $1$ |
特殊性質 A：保證 $\forall i\in[1,n-1]$，編號為 $i+1$ 的點的父節點為 $i$。
特殊性質 B：保證所有詢問均滿足 $u=1$。
特殊性質 C：保證所有詢問均滿足 $d\le 100$。
特殊性質 D：保證所有詢問均滿足 $d\ge 1000$。