呢題係互動題。
題目描述
畀定五元組 $(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$。對於任意 $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 恰好一次，然後呼叫 ask $q$ 次。互動程式庫會用特別嘅實作方式，單個 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 嘅方法類似，要註解掉第 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,\ldots,p_n$，分別代表 $2$ 到 $n$ 嘅父節點編號。本機除錯嗰陣，要保證對於所有 $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$ | $2\,000$ | |||
| $3,4$ | $10^5$ | $10^6$ | A | $5$ |
| $5,6$ | $6\times 10^4$ | $6\times 10^4$ | B | $50$ |
| $7$ | $5$ | |||
| $8$ | $10^5$ | $10^5$ | ||
| $9$ | $7\,500$ | $5\times 10^4$ | C | $500$ |
| $10$ | $10^4$ | D | ||
| $11$ | $15\,000$ | |||
| $12$ | $2\times 10^4$ | $50$ | ||
| $13$ | $25\,000$ | $5$ | ||
| $14$ | $3\times 10^4$ | $10^5$ | ||
| $15$ | $6\times 10^4$ | $10^6$ | ||
| $16$ | ||||
| $17$ | $8\times 10^4$ | |||
| $18$ | $10^5$ | |||
| $19$ | $1.5\times 10^5$ | |||
| $20$ | $2\times 10^5$ | $1$ |
特別性質 A：保證對於所有 $i\in[1,n-1]$，編號 $i+1$ 嘅點嘅父節點係 $i$。
特別性質 B：保證所有查詢都滿足 $u=1$。
特別性質 C：保證所有查詢都滿足 $d\le 100$。
特別性質 D：保證所有查詢都滿足 $d\ge 1000$。