Background

This is an interactive problem.

Before submitting this problem, please read the following carefully.

This problem only supports C++ submissions (C++14 is recommended; please do not use C++14 (GCC9)).

Due to Luogu’s special interaction mechanism, when submitting this problem, please remove the line #include "count.h" from your code, and paste the content of the provided file count_.h (note that it is not count.h inside count.zip) at the very beginning of your code, then submit.

If you cannot open count_.h, you may copy the following content.

#ifndef CIRCLE_H
#define CIRCLE_H
#include<vector>
struct info{
  unsigned val;
  unsigned poi[2];
};
const info emptyinfo=info{0,(unsigned)-1,(unsigned)-1};
info MR(info a,info b);
info MC(info a,info b);
void init(int T,int n,int q,std::vector<int>dad,std::vector<info>ve,int M);
bool isempty(info a);
info ask(int x,int d);

#endif

If anything unexpected happens when you submit this problem, please contact an administrator.

Problem Description

You are given a 5-tuple $(T, I, S_V, S_E, \iota)$, where:

• $T$ is a rooted tree with $n$ vertices, $T = (V, E)$, where $V$ is the vertex set and $E$ is the edge set. The vertices are numbered $1, 2, \ldots, n$, and the root is vertex $1$.
• $I$ is a set, whose elements are called information. There are two distinct special elements: the identity element $\epsilon$ and the invalid information $\bot$.

For general information, it has two attributes: a vertex set and an edge set. In particular, the identity element only has an edge-set attribute, while the invalid information has neither attribute.

• For information $o \in I \setminus \{ \epsilon, \bot \}$, the vertex set of $o$ is a 2-element subset of $V$, denoted $S_V(o)$, satisfying $S_V(o) \subseteq V$ and $\lvert S_V(o) \rvert = 2$. For two sets $A, B$, the difference $A \setminus B$ is defined as $A \setminus B = \{ x \in A \hspace{3mu}\vert\hspace{3mu} x \notin B \}$.
• For information $o \in I \setminus \{ \bot \}$, the edge set of $o$ is a subset of $E$, denoted $S_E(o)$, satisfying $S_E(o) \subseteq E$. The edge set of the identity element is defined to be empty, i.e. $S_E(\epsilon) = \varnothing$.
• For any edge $e \in E$ on the tree, let $e = (u, v)$. There exists an information $\iota(e) \in I$ associated with $e$, which takes its endpoints as the vertex set and itself as the edge set, i.e. $S_V(\iota(e)) = \{ u, v \}$ and $S_E(\iota(e)) = \{ e \}$.

There are two ways to merge information, denoted $R$ and $C$. For $\forall a, b \in I$, let $r = R(a, b)$ and $c = C(a, b)$, with $r, c \in I$. Then:

• Merging the identity element with any information yields the other one. That is, if $a = \epsilon$ then $r = c = b$; if $b = \epsilon$ then $r = c = a$.
• Merging invalid information with any information yields invalid information. That is, if $a = \bot$ or $b = \bot$, then $r = c = \bot$.
• In the remaining cases, if the intersection of the edge sets is non-empty, or the size of the intersection of the vertex sets is not $1$, then the merge result is invalid information. That is, if $S_E(a) \cap S_E(b) \ne \varnothing$ or $\lvert S_V(a) \cap S_V(b) \rvert \ne 1$, then $r = c = \bot$.
• Otherwise,$$S_E(r) = S_E(c) = S_E(a) \cup S_E(b) \text{,}$$ $$S_V(r) = S_V(a) \text{,}$$ $$S_V(c) = S_V(a) \oplus S_V(b) \text{,}$$ where $\oplus$ denotes symmetric difference, i.e. $A \oplus B = (A \cup B) \setminus (A \cap B)$.

Define the distance between two vertices in $T$ as the number of edges on the unique simple path between them.

You are given a scoring parameter $M$ and $q$ queries. Each query gives a vertex $u$ on the tree and a non-negative integer $d$. Let the vertex set $X$ be the set of all vertices in $T$ whose distance to $u$ is at most $d$. Let the edge set $Y = \{ (a, b) \in E \hspace{3mu}\vert\hspace{3mu} a, b \in X \}$ be the set of edges inside $X$. It can be proven that, starting from $\epsilon$ and all $\iota(e)$ ($e \in E$), it is always possible to obtain an information $o \ne \bot$ with $S_E(o) = Y$ using finitely many calls to $R$ and $C$.

For each query, you need to construct such an information $o$ under the constraint that the total number of calls to $R$ and $C$ is at most $M$. In particular, if $d = 0$, you may directly return the identity element $\epsilon$.

---

[Implementation Details]

Please make sure your program starts with #include "count.h".

The header file count.h implements the following:

1. Defines the data type info corresponding to information.

2. Defines the info constant emptyinfo corresponding to $\epsilon$, which you may directly use in your program.

3. Defines and implements the following two merge functions, which you may directly call:

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

   • These two functions return the information corresponding to $R(a, b)$ and $C(a, b)$, respectively.

   You must ensure that when calling $\boldsymbol{R(a, b)}$ and $\boldsymbol{C(a, b)}$, the result is not $\boldsymbol{\bot}$, otherwise the program may behave abnormally.

4. Defines and implements a function to check whether an information is the identity element, which you may directly call:

   bool isempty(info a);
   

   • This function returns true if and only if $a$ is the identity element.

You may refer to the reference interactive library for more implementation details.

You do not need to, and should not, implement main(). You need to implement the following functions:

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

• T is the test point id, n is the number of vertices, q is the number of queries, and M is the scoring parameter for this test point.
• The lengths of fa and e are both $n - 1$. For $0 \le i < n - 1$, $fa[i]$ and $i + 2$ are the endpoints of the $i$-th edge $e_i$, and e[i] is the info element corresponding to $\iota(e_i)$ described above. The data guarantees that $fa[i]$ is less than $i + 2$.

info ask(int u, int d);

This gives a query; the meaning of the parameters is as described above. You need to return an information that satisfies the requirements at the end of the function.

In the final test, for each test point, the interactive library will call init exactly once, and then call ask $q$ times. The interactive library uses a special implementation: a single variable of type info will always consume $12$ bytes of memory, which is different from the provided reference interactive library. To ensure the runtime memory usage stays within the limit, you need to make sure that there are not too many info variables existing simultaneously during execution.

It is guaranteed that, under the call limit and without calling isempty, the final interactive library runs in at most 0.6 seconds, and the library itself uses at most 16 MiB of memory. It is also guaranteed that, when only executing ${10}^8$ calls to isempty, the final interactive library runs in at most 0.25 seconds.

The provided files include count.cpp as a sample program, which contestants may continue implementing based on it. The provided files also include a backup file count_backup.h; we guarantee it is exactly the same as count.h.

---

[How to Run the Test Program]

This problem directory provides two reference implementations of the interactive library, grader.o and checker.o, which are linkable files compiled from two different libraries. The interactive library used in the final test is different from these implementations, so your solution must not depend on the specific implementation details of the library, and also must not depend on the specific implementation of the info type in count.h.

You need to modify the provided count.h to help with linking. Specifically, when linking count.cpp with grader.o, you need to comment out line 5 of count.h and keep line 4. Linking with checker.o is similar: you need to comment out line 4 and keep line 5. Contestants may modify the implementation of count.h to compile different programs.

After modification, you can compile an executable in this directory using:

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

The first command compiles count.cpp and links it with grader.o to produce count. The second command links it with checker.o to produce count.

The executable count produced as above runs as follows:

• It reads input from standard input in the following format:
  • The first line contains four integers $id, n, q, M$, which are the test point id, the number of vertices, the number of queries, and the scoring parameter.
  • The second line contains $n - 1$ integers $p_2, p_3, \ldots, p_n$, which are the parent indices of vertices $2$ through $n$. When debugging locally, you need to ensure that for all $\forall i \in [2, n]$, $p_i < i$.
  • The next $q$ lines each contain two integers $u, d$, describing a query.
• After reading, the interactive library will run the test. If your program does not satisfy the library constraints, it will output corresponding error messages. Otherwise, for the linked executable, it outputs:
  • One line with three integers $C_1, C_2, C_3$, where:
    • $C_1$ is the total number of interactive-library function calls made within init.
    • $C_2$ is the total number of interactive-library function calls made during the whole run.
    • $C_3$ is the maximum number of interactive-library function calls made within the $q$ calls to ask.
    • For these three statistics, we only count calls to MR and MC, and do not count calls to isempty.
• When linking different files, the checks performed are different:
  • grader.o: it does not check whether the info returned by ask is correct, but it can help contestants determine whether the interaction operations meet the requirements. Its runtime is closest to the interactive library used in judging, so it can be used to test speed, but correctness is not guaranteed.
  • checker.o: it checks whether the info returned by ask is correct, and can also help contestants determine whether interaction operations meet the requirements. It also checks whether the info returned by ask is correct. This program can verify answer correctness.

When debugging, you must ensure that the input to the executable count satisfies the format above; otherwise the output is not guaranteed to be correct.

Input Format

See [How to Run the Test Program].

Output Format

See [How to Run the Test Program].

Hint

Idea: zx2003, Solution: zx2003, Code: zx2003, Data: zx2003.

[Scoring]

In the final judging, only count.cpp will be collected. Modifying other files in your directory will not affect the judging result. Note:

• An uninitialized variable of type info is not guaranteed to be emptyinfo.
• Please do not try to access or modify member variables of info, otherwise it will be considered an attack on the interactive library.
• Do not call MR or MC before init is called, otherwise undefined behavior may occur.
• You may only access variables you define yourself and info variables returned by the interactive library; attempting to access other memory may cause compilation errors or runtime errors.

This problem is first subject to the same limits as traditional problems, for example, compilation errors will cause the whole problem to score 0 points, runtime errors, exceeding time limits, exceeding memory limits, etc. will cause corresponding test points to score 0 points, and so on.

Besides the above conditions, within a test point, if the program makes illegal function calls or gives an incorrect answer in any query operation, that test point will score 0 points. Otherwise, let $C_1$ and $C_3$ be the number of interactive-library function calls in init, and the maximum number of interactive-library function calls among all $q$ calls to ask, respectively. If $C_1 \le 3 \cdot {10}^7$ and $C_3$ does not exceed the scoring parameter $M$ of that test point, you will receive the score for that test point; otherwise you will not. Note: when computing $C_1$ and $C_3$, only calls to MR and MC are counted, and calls to isempty are not counted.

---

[Sample #1]

See count/count1.in and count/count1.ans in the attachments.

---

[Sample #2]

See count/count2.in and count/count2.ans in the attachments.

This sample satisfies the special property A in the Constraints.

---

[Sample #3]

See count/count3.in and count/count3.ans in the attachments.

This sample satisfies the special property B in the Constraints.

---

[Sample #4]

See count/count4.in and count/count4.ans in the attachments.

---

[Constraints]

For all test points, $1 \le n \le 2 \times {10}^5$ and $1 \le q \le {10}^6$. In each query, $1 \le u \le n$ and $1 \le d \le n - 1$.

Test point	$n=$	$q=$	Special property	$M=$
$1$	$1000$	$10^4$		$500$
$2$	$2000$
$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$		$5$
$8$	$10^5$
$9$	$7500$	$5 \times 10^4$	C	$500$
$10$	$10^4$
$11$	$1.5 \times 10^4$
$12$	$2 \times 10^4$			$50$
$13$	$2.5 \times 10^4$			$5$
$14$	$3 \times 10^4$	$10^5$
$15$	$6 \times 10^4$	$10^6$	D
$16$
$17$	$8 \times 10^4$
$18$	$10^5$
$19$	$1.5 \times 10^5$
$20$	$2 \times 10^5$			$1$

Special property A: guarantees that for all $\forall i \in [1, n - 1]$, the parent of vertex $i + 1$ is vertex $i$.
Special property B: guarantees that all queries satisfy $u = 1$.
Special property C: guarantees that all queries satisfy $d \le 100$.
Special property D: guarantees that all queries satisfy $d \ge 1000$.

Translated by ChatGPT 5