P8498 [NOI2022] Neighborhood Point Counting on a Tree.

**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. ```cpp #ifndef CIRCLE_H #define CIRCLE_H #include 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::vectordad,std::vectorve,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.

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: ```cpp 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: ```cpp 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: ```cpp void init(int T, int n, int q, vector fa, vector 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$. ```cpp 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: ```bash 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.

See [How to Run the Testing Program].

See [How to Run the Testing Program].

**[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$ | $10^4$ | | $500$ | | $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$ | $6 \times 10^4$ | B | $5$ | | $8$ | $10^5$ | $10^5$ | B | $5$ | | $9$ | $7500$ | $5 \times 10^4$ | C | $500$ | | $10$ | $10^4$ | $5 \times 10^4$ | | $500$ | | $11$ | $1.5 \times 10^4$ | $5 \times 10^4$ | | $500$ | | $12$ | $2 \times 10^4$ | $5 \times 10^4$ | | $50$ | | $13$ | $2.5 \times 10^4$ | $5 \times 10^4$ | | $5$ | | $14$ | $3 \times 10^4$ | $10^5$ | | $5$ | | $15$ | $6 \times 10^4$ | $10^6$ | D | $5$ | | $16$ | $6 \times 10^4$ | $10^6$ | | $5$ | | $17$ | $8 \times 10^4$ | $10^6$ | | $5$ | | $18$ | $10^5$ | $10^6$ | | $5$ | | $19$ | $1.5 \times 10^5$ | $10^6$ | | $5$ | | $20$ | $2 \times 10^5$ | $10^6$ | | $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