題目背景

呢題係一道互動題。

偉大嘅科學家欣準備建造強人工智能隆嚟統治世界。輸入咗一啲越南嘅算法競賽題做訓練集之後，佢發現隆自動生成咗一個新問題，仲畀咗一份解答。同時，隆仲將測試集入面 30% 嘅輸入數據歸約到呢個問題。 欣即刻將呢個問題抄低如下： 畀定一棵有根樹，你需要支援兩種操作：

• 查詢樹鏈元素和
• 將一個點嘅父節點改成另一個點

「呢個問題唔算難呀，點解可以解決測試集入面 30% 嘅問題呢？」欣心諗。 喺關閉訓練結果頁面之前，欣突然發現，隆畀出嘅呢個問題入面，資訊合併嘅成本並唔係 $O(1)$。 欣陷入沉思，發現自己唔識做呢題。 為咗知道呢題有幾難，欣將呢題擺到你面前。

題目描述

你需要維護一棵以 $1$ 為根嘅有根樹。呢棵樹有 $n$ 個點。初始時，對所有 $2 \le i \le n$，點 $i$ 有一個父節點 $p_i$，保證 $p_i \lt i$。

一開始你有 $n$ 個集合 $\{1\},\{2\},\cdots,\{n\} $。對任何兩個集合 $A$ 同 $B$，如果 $A \cap B=\varnothing$，咁你可以透過一次操作，花費 $|A|+|B|$ 嘅成本，獲得集合 $A \cup B$。

之後有 $q$ 次操作。每次操作有兩種類型：

• 0 a b 設樹上由 $a$ 到 $b$ 嘅路徑上嘅點構成嘅點集為 $S$。你需要將 $S$ 表示成 $\cup_{i=1}^{k}A_i$，當中要滿足 $A_i$ 係你已經獲得嘅集合，而且 $\forall i \neq j,A_i \cap A_j=\varnothing$。用 $(A_1,A_2,\cdots,A_k) $ 回答一次查詢嘅成本係 $k$。
• 1 a b 表示將點 $a$ 嘅父節點改成 $b$，保證 $a \gt 1$，而且修改之後呢 $n$ 個點仍然構成一棵樹，但唔保證 $a \gt b$。你可以喺今次操作入面生成一啲新集合，用嚟應付之後嘅查詢。

設你成個程式運行期間花費嘅總成本為 $C_1$，單次操作成本嘅最大值為 $C_2$。每個子任務會按照 $C_1,C_2$ 嘅大小，以指定方式評分。

實作細節

請確保你嘅程式開頭有 #include "long.h"。

標頭檔入面定義咗資料類型 infoset，用嚟儲存你獲得嘅集合。

呢個類型包含成員函式 size()，表示集合大小。標頭檔仲提供咗表示空集嘅常量 emptyset。

另外，你仲可以呼叫以下函式：

infoset merge(const infoset&A,const infoset&B);

• 花費一定成本生成一個新集合 $A \cup B$
• 留意，你可以重複生成同一個集合多次，而成本亦需要計算多次

void report(infoset A);

• 你只可以喺查詢操作期間呼叫呢個函式，表示花費 $1$ 嘅成本，喺最終嘅聯集入面加入一個集合 $A$

你唔需要，亦唔應該實作主函式。你需要實作以下幾個函式：

void init(int id,int n,int q,vector<int>dad,vector<infoset>ve);

• 你可以喺 $q$ 次操作開始之前預處理一啲資訊
• 喺呢個函式入面花費嘅成本唔會計入單次操作成本嘅最大值，但會計入成個程式運行期間花費嘅總成本
• id 表示子任務編號，n 表示總點數，q 表示總操作數
• dad 嘅大小係 $n-1$，dad[i] 表示初始時點 $i+2$ 嘅父節點
• ve 嘅大小係 $n$，ve[i] 表示初始集合 $\{i+1\}$

void modify(int x,int y);

• 執行一次修改操作，將點 $x$ 嘅父節點設為點 $y$

void ask(int x,int y);

• 執行一次查詢操作，查詢由 $x$ 到 $y$ 嘅樹鏈資訊
• 你需要呼叫 report 若干次嚟回答查詢；今次查詢結束時，互動程式庫會檢查你回報嘅所有集合 $A$ 係咪符合條件

評測時，互動程式庫會先呼叫 init 一次，之後總共呼叫 modify 同 ask $q$ 次。

本題保證樹嘅形態同要執行嘅操作喺互動開始之前已經完全確定，唔會按照同你程式嘅互動過程動態構造。因此，題目入面嘅互動操作全部都係確定性嘅，你唔需要理會呢啲操作喺互動程式庫入面嘅具體實作。

評測時，互動程式庫會用特殊嘅實作方式，單個 infoset 類型變數固定佔用 $8$ 位元組記憶體。請確保程式運行期間唔會同時存在太多 infoset 類型嘅變數。

保證喺呼叫次數限制之內，互動程式庫所需運行時間唔超過 2s；互動程式庫本身佔用嘅記憶體唔超過 16MB。

測試程式方法

派發檔案入面嘅 grader.cpp 係我哋提供嘅互動程式庫參考實作。最終測試用嘅互動程式庫實作同呢份參考實作有所不同，所以參賽者嘅解法唔應該依賴互動程式庫嘅實作。

你需要用以下指令編譯出可執行程式： g++ grader.cpp long.cpp -o long -static -O2 -std=c++14

對編譯出嚟嘅可執行程式：

• 可執行檔會由標準輸入讀入以下格式嘅數據：
  • 第一行包含一個整數 $id$，表示子任務編號
  • 第二行包含兩個整數 $n,q$，表示總點數同總操作數
  • 第三行包含 $n-1$ 個整數，分別表示第 $2$ 至 $n$ 個點嘅父節點編號
  • 之後 $q$ 行，每行三個整數 $op,x,y$，描述一次操作。$op=0$ 表示查詢操作，$op=1$ 表示修改操作
• 讀入完成之後，互動程式庫會恰好呼叫 init 一次，同埋 modify 或 ask $q$ 次，用輸入數據測試你嘅函式。程式正常運行之後會輸出若干行，每行若干個數，表示你對每次查詢操作畀出嘅答案；最後一行會包含兩個整數 $W_1,W_2$，分別表示程式運行花費嘅總成本，同埋單次操作成本嘅最大值。

派發檔案包含四組樣例檔案，當中第四組樣例符合子任務二嘅特殊性質。測試樣例時，請忽略輸出檔案最後一行嘅比較結果，因為互動程式庫輸出嘅最後一行係程式運行成本，唔係查詢操作嘅查詢結果。

評分方式

本題首先會受到同傳統題一樣嘅限制。例如，編譯錯誤會令成題得 $0$ 分；運行時錯誤、超過時間限制、超過記憶體限制等，會令相應測試點得 $0$ 分。你只可以存取自己定義嘅變數、互動程式庫提供嘅變數，以及佢哋對應嘅記憶體空間；嘗試存取其他空間可能會導致編譯錯誤或者運行錯誤。

喺以上條件之下，對一個測試點，如果程式執行咗非法函式呼叫、冇正常結束運行，或者對查詢操作畀出錯誤答案，呢個測試點會得 $0$ 分。否則，會按照程式花費嘅成本，用以下兩種方式之一評分：

• 評測方式一：如果 $W_1 \gt 6 \cdot 10^8$，呢個測試點得 $0$ 分；否則，呢個測試點嘅得分係 $\frac{\frac{1.5 \cdot 10^8}{max(W_1,1.5 \cdot 10^8)} \cdot 7+3}{10} \times \text{呢個測試點所屬子任務嘅分值}$
• 評測方式二：如果 $W_2 \gt 2 \cdot 10^4$，呢個測試點得 $0$ 分；否則，呢個測試點嘅得分係 $\frac{5000}{max(W_2,5000)} \times \text{呢個測試點所屬子任務嘅分值}$

唔同子任務會用唔同評測方式。一個子任務嘅得分係當中所有測試點得分嘅最小值。

限制與約定

保證所有測試點都有 $1 \le n,q \le 10^5$。

特殊性質：保證任何時刻，除咗 $1$ 號節點之外，每個節點最多只有一個子節點。

時間限制：$10s$

記憶體限制：$1024MB$

後記

欣發現你用咗五個鐘都仲未做出呢題，對隆嘅能力感到好滿意。不過，第二朝起身之後，欣突然發現隆嘅做法嘅複雜度證明係錯嘅。