Đây là một bài toán tương tác.

Cho bộ năm $(T,I,S_V,S_E,\iota)$, trong đó:

• $T$ là một cây có gốc gồm $n$ đỉnh, $T=(V,E)$, với $V$ là tập đỉnh và $E$ là tập cạnh của $T$. Các đỉnh được đánh số $1,2,\ldots,n$, và đỉnh gốc có số hiệu $1$.
• $I$ là một tập hợp, các phần tử của nó được gọi là thông tin. Trong đó có hai phần tử đặc biệt khác nhau: phần tử đơn vị $\varepsilon$ và thông tin không hợp lệ $\bot$.

Mỗi thông tin thông thường có hai thuộc tính: tập đỉnh và tập cạnh. Riêng phần tử đơn vị chỉ có thuộc tính tập cạnh; thông tin không hợp lệ không có cả hai thuộc tính này.

• Với thông tin $o\in I\setminus\{\varepsilon,\bot\}$, tập đỉnh của $o$ là một tập con gồm hai phần tử của $V$, ký hiệu $S_V(o)$, thỏa mãn $S_V(o)\subseteq V$ và $|S_V(o)|=2$. Hiệu $A\setminus B$ của hai tập hợp $A,B$ được định nghĩa là $A\setminus B=\{x\in A\mid x\notin B\}$.
• Với thông tin $o\in I\setminus\{\bot\}$, tập cạnh của $o$ là một tập con của $E$, ký hiệu $S_E(o)$, thỏa mãn $S_E(o)\subseteq E$. Quy ước tập cạnh của phần tử đơn vị là tập rỗng, tức $S_E(\varepsilon)=\varnothing$.
• Với mỗi cạnh $e\in E$ của cây, ký hiệu $e=(u,v)$, tồn tại một thông tin $\iota(e)\in I$ tương ứng với $e$, có tập đỉnh là hai đầu mút của cạnh và tập cạnh là chính cạnh đó, tức $S_V(\iota(e))=\{u,v\}$, $S_E(\iota(e))=\{e\}$.

Có hai cách hợp nhất thông tin, ký hiệu lần lượt là $R$ và $C$. Với mọi $a,b\in I$, đặt $r=R(a,b)$, $c=C(a,b)$, thỏa mãn $r,c\in I$, ta có:

• Hợp nhất phần tử đơn vị với bất kỳ thông tin nào đều cho thông tin còn lại. Cụ thể, nếu $a=\varepsilon$ thì $r=c=b$; nếu $b=\varepsilon$ thì $r=c=a$.
• Hợp nhất thông tin không hợp lệ với bất kỳ thông tin nào đều cho thông tin không hợp lệ. Cụ thể, nếu $a=\bot$ hoặc $b=\bot$ thì $r=c=\bot$.
• Trong các trường hợp còn lại, nếu giao hai tập cạnh khác rỗng, hoặc giao hai tập đỉnh không có đúng một phần tử, thì kết quả hợp nhất là thông tin không hợp lệ. Cụ thể, nếu $S_E(a)\cap S_E(b)\ne\varnothing$ hoặc $|S_V(a)\cap S_V(b)|\ne1$ thì $r=c=\bot$.
• Nếu không, ta có

$$ 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). $$

Ở đây $\oplus$ là phép hiệu đối xứng của hai tập hợp, tức $A\oplus B=(A\cup B)\setminus(A\cap B)$.

Định nghĩa khoảng cách trên cây giữa hai đỉnh của $T$ là số cạnh trên đường đi đơn duy nhất có hai đỉnh ấy làm đầu mút.

Cho tham số tính điểm $M$ và $q$ truy vấn. Mỗi truy vấn cho một đỉnh $u$ trên cây và một số nguyên không âm $d$. Gọi $X$ là tập hợp tất cả các đỉnh có khoảng cách trên cây tới $u$ không vượt quá $d$, và $Y=\{(a,b)\in E\mid a,b\in X\}$ là tập cạnh bên trong $X$. Có thể chứng minh rằng, bắt đầu từ $\varepsilon$ và tất cả $\iota(e)$ với $e\in E$, luôn có thể thực hiện hữu hạn phép $R,C$ để thu được thông tin $o\ne\bot$ thỏa mãn $S_E(o)=Y$.

Với mỗi truy vấn, bạn cần tạo ra một thông tin $o$ như vậy bằng tổng số lần gọi $R$ và $C$ không vượt quá $M$. Đặc biệt, nếu $d=0$ thì trả về trực tiếp phần tử đơn vị $\varepsilon$.

Chi tiết cài đặt

Hãy bảo đảm đầu chương trình có #include "count.h".

Tệp tiêu đề count.h cài đặt các nội dung sau:

1. Định nghĩa kiểu dữ liệu info tương ứng với thông tin.
2. Định nghĩa hằng số kiểu info tên emptyinfo tương ứng với $\varepsilon$, có thể dùng trực tiếp trong chương trình.
3. Định nghĩa và cài đặt hai hàm hợp nhất thông tin sau, có thể gọi trực tiếp trong chương trình:

info MR(info a,info b);
info MC(info a,info b);

• Hai hàm lần lượt trả về thông tin tương ứng với $R(a,b)$ và $C(a,b)$.

Bạn phải bảo đảm kết quả khi gọi $R(a,b)$ hoặc $C(a,b)$ không phải là $\bot$, nếu không chương trình có thể hoạt động bất thường.

1. Định nghĩa và cài đặt hàm sau để kiểm tra một thông tin có phải là phần tử đơn vị hay không; có thể gọi trực tiếp trong chương trình:

bool isempty(info a);

• Hàm này trả về đúng khi và chỉ khi $a$ là phần tử đơn vị.

Bạn có thể xem thư viện tương tác tham khảo để biết thêm chi tiết cài đặt.

Bạn không cần và cũng không được cài đặt hàm chính. Bạn cần cài đặt các hàm sau:

void init(int T, int n, int q, vector<int> fa, vector<info> e, int
  M);

• T là số hiệu bộ kiểm thử, n là số đỉnh của cây, q là số truy vấn, M là tham số tính điểm của bộ kiểm thử.
• fa và e có độ dài $n-1$. Với $0\le i<n-1$, fa[i] và $i+2$ là hai đầu mút của cạnh thứ $i$, ký hiệu $e_i$; e[i] là phần tử kiểu info tương ứng với $\iota(e_i)$ được mô tả trong đề. Dữ liệu bảo đảm fa[i] nhỏ hơn $i+2$.

info ask(int u, int d);

• Cho một truy vấn, với ý nghĩa các tham số như trong mô tả bài toán. Khi hàm kết thúc, bạn cần trả về một thông tin thỏa mãn điều kiện của đề.

Trong kiểm thử chính thức, với mỗi bộ kiểm thử, thư viện tương tác sẽ gọi hàm init đúng một lần, sau đó gọi hàm ask tổng cộng $q$ lần. Thư viện tương tác sử dụng một cách cài đặt đặc biệt: mỗi biến kiểu info luôn chiếm 12 byte bộ nhớ, khác với thư viện tham khảo được cung cấp. Để bảo đảm mức sử dụng bộ nhớ khi chạy nằm trong giới hạn của đề, bạn cần tránh có quá nhiều biến kiểu info cùng tồn tại.

Bảo đảm rằng khi đáp ứng giới hạn số lần gọi và không gọi hàm isempty, thời gian chạy của thư viện tương tác chính thức không vượt quá $0.6$ giây, và bộ nhớ do bản thân thư viện sử dụng không vượt quá 16 MiB. Bảo đảm rằng nếu chỉ thực hiện $10^8$ lần gọi isempty, thời gian chạy của thư viện tương tác chính thức không vượt quá $0.25$ giây.

Trong các tệp được cung cấp có một tệp tên count.cpp làm chương trình mẫu; bạn có thể tiếp tục cài đặt dựa trên chương trình này. Trong các tệp còn có một bản sao lưu tên count_backup.h, được bảo đảm hoàn toàn giống với count.h.

Cách kiểm thử chương trình

Trong thư mục của bài có hai bản cài đặt tham khảo của thư viện tương tác, grader.o và checker.o; đây là các tệp có thể liên kết, được biên dịch từ hai thư viện tương tác khác nhau. Cách cài đặt thư viện dùng khi kiểm thử chính thức khác với chúng, vì vậy lời giải của bạn không được phụ thuộc vào cách cài đặt cụ thể của thư viện tương tác, cũng không được phụ thuộc vào cách cài đặt cụ thể của kiểu info trong count.h.

Bạn cần sửa tệp count.h được cung cấp để hỗ trợ liên kết. Cụ thể, khi liên kết mã nguồn count.cpp với chương trình grader.o, bạn cần biến dòng 5 của count.h thành chú thích và giữ dòng 4. Cách liên kết checker.o tương tự: biến dòng 4 của count.h thành chú thích và giữ dòng 5. Bạn có thể sửa cách cài đặt count.h để biên dịch các chương trình khác nhau.

Sau khi sửa, bạn có thể dùng các lệnh sau trong thư mục của bài để tạo chương trình thực thi:

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

Lệnh thứ nhất biên dịch count.cpp hiện tại rồi liên kết với grader.o để tạo tệp thực thi count; lệnh thứ hai biên dịch count.cpp hiện tại rồi liên kết với checker.o để tạo tệp thực thi count.

Tệp thực thi count được biên dịch và liên kết theo cách trên hoạt động như sau:

• Tệp thực thi đọc dữ liệu từ đầu vào chuẩn theo định dạng sau:
  • Dòng đầu có bốn số nguyên $id,n,q,M$, lần lượt là số hiệu bộ kiểm thử, số đỉnh của cây, số truy vấn và tham số tính điểm.
  • Dòng thứ hai có $n-1$ số nguyên $p_2,p_3,\ldots,p_n$, lần lượt là số hiệu đỉnh cha của các đỉnh từ $2$ tới $n$. Khi kiểm thử cục bộ, bạn phải bảo đảm với mọi $i\in[2,n]$, $p_i<i$.
  • Tiếp theo là $q$ dòng, mỗi dòng có hai số nguyên $u,d$, mô tả một truy vấn.
• Sau khi đọc, thư viện tương tác tiến hành kiểm thử. Nếu chương trình của bạn không đáp ứng các hạn chế của thư viện, nó sẽ xuất thông báo lỗi tương ứng. Nếu không, đối với tệp thực thi được liên kết, kết quả xuất ra như sau:
  • Một dòng gồm ba số nguyên $C_1,C_2,C_3$, trong đó:
    • $C_1$ là tổng số lần chương trình gọi hàm của thư viện tương tác trong hàm init.
    • $C_2$ là tổng số lần chương trình gọi hàm của thư viện tương tác trong toàn bộ quá trình chạy.
    • $C_3$ là số lần gọi hàm của thư viện tương tác lớn nhất trong $q$ lần gọi hàm ask.
    • Đối với cả ba đại lượng trên, chỉ tính số lần gọi MR, MC, không tính số lần gọi isempty.
• Khi liên kết với các tệp khác nhau, các phép kiểm tra có thể thực hiện cũng khác nhau. Cụ thể:
  • grader.o: khi chạy sẽ không kiểm tra thông tin hàm ask trả về có đúng hay không, nhưng giúp bạn kiểm tra các thao tác tương tác có đáp ứng yêu cầu hay không. Thời gian chạy của chương trình này gần với thư viện tương tác chính thức nhất, vì vậy bạn có thể dùng nó để kiểm tra tốc độ chạy, nhưng nó không bảo đảm tính đúng đắn của chương trình.
  • checker.o: khi chạy sẽ kiểm tra thông tin hàm ask trả về có đúng hay không, đồng thời giúp bạn kiểm tra các thao tác tương tác có đáp ứng yêu cầu hay không. Nó cũng kiểm tra thông tin hàm ask trả về có đúng hay không. Chương trình này có thể dùng để kiểm tra tính đúng đắn của đáp án.

Khi kiểm thử, bạn cần bảo đảm dữ liệu đưa vào tệp thực thi count đáp ứng định dạng đầu vào nêu trên; nếu không, kết quả xuất ra không được bảo đảm đúng.

Ví dụ 1

Xem count/count1.in và count/count1.ans trong thư mục dành cho thí sinh.

Ví dụ 2

Xem count/count2.in và count/count2.ans trong thư mục dành cho thí sinh.

Bộ ví dụ này thỏa mãn tính chất đặc biệt A trong phần giới hạn dữ liệu.

Ví dụ 3

Xem count/count3.in và count/count3.ans trong thư mục dành cho thí sinh.

Bộ ví dụ này thỏa mãn tính chất đặc biệt B trong phần giới hạn dữ liệu.

Ví dụ 4

Xem count/count4.in và count/count4.ans trong thư mục dành cho thí sinh.

Nhiệm vụ con

Khi chấm chính thức, chỉ thu nhận count.cpp; việc sửa các tệp khác trong thư mục dành cho thí sinh không ảnh hưởng đến kết quả chấm. Lưu ý:

• Biến kiểu info chưa được khởi tạo không được bảo đảm là emptyinfo.
• Không được truy cập hoặc sửa các biến thành viên của kiểu info; làm như vậy sẽ bị xem là tấn công thư viện tương tác.
• Không gọi MR và MC trước khi hàm init được gọi, vì có thể gây ra hành vi không xác định.
• Bạn chỉ được truy cập các biến do mình định nghĩa và các biến kiểu info do thư viện tương tác trả về; cố truy cập không gian bộ nhớ khác có thể dẫn đến lỗi biên dịch hoặc lỗi khi chạy.

Bài này trước hết chịu các giới hạn giống bài toán truyền thống. Chẳng hạn, lỗi biên dịch khiến toàn bộ bài được 0 điểm; lỗi khi chạy, vượt giới hạn thời gian, vượt giới hạn bộ nhớ, v.v. khiến bộ kiểm thử tương ứng được 0 điểm.

Ngoài các điều kiện trên, trong một bộ kiểm thử, nếu chương trình thực hiện lời gọi hàm không hợp lệ hoặc trả về đáp án sai cho một truy vấn, bộ kiểm thử đó được 0 điểm. Nếu không, gọi $C_1$ là số lần chương trình gọi hàm của thư viện tương tác trong init, và $C_3$ là số lần gọi hàm của thư viện tương tác lớn nhất trong tất cả $q$ lần gọi ask. Nếu $C_1\le3\cdot10^7$ và $C_3$ không vượt quá tham số tính điểm $M$ của bộ kiểm thử, bạn nhận được điểm của bộ kiểm thử đó; nếu không thì không nhận được điểm của bộ kiểm thử đó. Lưu ý: khi tính $C_1,C_3$, chỉ tính số lần gọi MR, MC, không tính số lần gọi isempty.

Giới hạn

Với mọi bộ kiểm thử, $1\le n\le2\cdot10^5$, $1\le q\le10^6$; trong mỗi truy vấn, $1\le u\le n$, $1\le d\le n-1$.

Tính chất đặc biệt A: Bảo đảm với mọi $i\in[1,n-1]$, cha của đỉnh có số hiệu $i+1$ là $i$.

Tính chất đặc biệt B: Bảo đảm mọi truy vấn đều thỏa mãn $u=1$.

Tính chất đặc biệt C: Bảo đảm mọi truy vấn đều thỏa mãn $d\le100$.

Tính chất đặc biệt D: Bảo đảm mọi truy vấn đều thỏa mãn $d\ge1000$.