Background

This is an interactive problem.

Before submitting this problem, please read the following carefully.

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

Due to Luogu’s special interactive 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 the 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 the administrator.

Problem Description

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

• $T$ is a rooted tree with $n$ nodes, $T = (V, E)$, where $V$ is the vertex set of $T$ and $E$ is the edge set of $T$. The nodes are numbered $1, 2, \ldots, n$, and the root is node $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 ordinary information, it has two attributes: a vertex set and an edge set. In particular, the identity element only has the edge-set attribute, while the invalid information has neither of the above attributes.

• For information $o \in I \setminus \{ \epsilon, \bot \}$, the vertex set of $o$ is a 2-element subset of $V$, denoted by $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 by $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, write $e = (u, v)$. There exists information $\iota(e) \in I$ about $e$, whose vertex set is its endpoints and whose edge set is itself, i.e. $S_V(\iota(e)) = \{ u, v \}$ and $S_E(\iota(e)) = \{ e \}$.

There are two ways to merge information, denoted by $R$ and $C$. For $\forall a, b \in I$, let $r = R(a, b), c = C(a, b)$, where $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 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.

Given a scoring parameter $M$ and $q$ queries, each query provides a node $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, through a finite number of calls to $R$ and $C$, to obtain information $o \ne \bot$ such that $S_E(o) = Y$.

For each query, you need to construct such 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 can directly return the identity element $\epsilon$.

---

[Implementation Details]

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

The header count.h implements the following:

1. Defines the data type info corresponding to information.

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

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

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

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

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

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

   bool isempty(info a);
   

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

You can check the reference interactive library for more implementation details.

You do not need, and should not, implement the main function. 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 nodes, 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)$ mentioned in the statement. The data guarantees that $fa[i]$ is less than $i + 2$.

info ask(int u, int d);

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

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 always consumes $12$ bytes of memory, which is different from the provided reference interactive library. To keep the runtime memory usage within the limit, you need to ensure that not too many variables of type info exist at the same time during execution.

It is guaranteed that, when satisfying the call limit and without calling isempty, the time needed by the final interactive library does not exceed 0.6 seconds, and the memory used by the interactive library itself does not exceed 16 MiB. It is guaranteed that, when only executing ${10}^8$ calls to isempty, the running time of the final interactive library does not exceed 0.25 seconds.

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

---

[How to Run the Testing Program]

This problem directory provides two reference implementations of the interactive library, grader.o and checker.o, which are linkable files produced by compiling two different interactive libraries. The interactive library used in the final test is different from these implementations, so your solution must not depend on the specific implementation of the interactive 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 the source code 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. You may modify the implementation in count.h to compile different programs.

After modification, you can compile an executable in this directory with the following commands:

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 an executable count. The second command compiles count.cpp and links it with checker.o to produce an executable count.

The executable count compiled 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$, representing the test point id, the number of nodes, the number of queries, and the scoring parameter.
  • The second line contains $n - 1$ integers $p_2, p_3, \ldots, p_n$, representing the parent of nodes $2$ to $n$. When debugging locally, you need to ensure that $\forall i \in [2, n]$, $p_i < i$.
  • The next $q$ lines each contain two integers $u, d$, describing one query.
• After reading, the interactive library performs testing. If your program does not satisfy the library’s constraints, it will output the corresponding error message. Otherwise, for the linked executable, it outputs:
  • A single line with three integers $C_1, C_2, C_3$, where:
    • $C_1$ is the total number of calls to interactive-library functions made in init.
    • $C_2$ is the total number of calls to interactive-library functions made during the whole run.
    • $C_3$ is the maximum, over the $q$ calls to ask, of the number of calls to interactive-library functions made within a single ask.
    • For these three statistics, only calls to MR and MC are counted; calls to isempty are not counted.
• When linking different files, the checks performed are also different:
  • grader.o: it does not check whether the information returned by ask is correct, but it can help contestants verify whether the interactive operations meet the requirements. Its running time is the closest to that of the interactive library in evaluation, so contestants can use it to test speed, but correctness is not guaranteed.
  • checker.o: it checks whether the information returned by ask is correct, and can also help contestants verify whether the interactive operations meet the requirements. It also checks whether the information returned by ask is correct. This program can be used to check answer correctness.

When debugging, you need to ensure that the input to the executable count satisfies the input format above; otherwise, the correctness of the output is not guaranteed.

Input Format

See [How to Run the Testing Program].

Output Format

See [How to Run the Testing Program].

Hint

[Scoring]

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

• An uninitialized variable of type info is not guaranteed to be emptyinfo.
• 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 variables of type info returned by the interactive library. Attempting to access other memory may cause a compilation error or a runtime error.

This problem is first subject to the same constraints as traditional problems, e.g. a compilation error yields 0 points for the whole problem; runtime error, time limit exceeded, memory limit exceeded, etc. yield 0 points for the corresponding test point.

Besides the above conditions, within a test point, if the program performs illegal function calls or provides a wrong answer in a query operation, that test point will receive 0 points. Otherwise, let $C_1$ and $C_3$ be the number of calls to interactive-library functions in init, and the maximum, over all $q$ calls to ask, of the number of calls to interactive-library functions within a single ask. If $C_1 \le 3 \cdot {10}^7$ and $C_3$ does not exceed the scoring parameter $M$ of that test point, you will get the score of that test point; otherwise, you will not get the score of that test point. Note that, when computing $C_1$ and $C_3$, only calls to MR and MC are counted; 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 special property A in the Constraints.

---

[Sample #3]

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

This sample satisfies 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$, $1 \le q \le {10}^6$. In each query, $1 \le u \le n$, $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: It is guaranteed that $\forall i \in [1, n - 1]$, the parent of node $i + 1$ is node $i$.
Special property B: It is guaranteed that all queries satisfy $u = 1$.
Special property C: It is guaranteed that all queries satisfy $d \le 100$.
Special property D: It is guaranteed that all queries satisfy $d \ge 1000$.

Translated by ChatGPT 5