Background

1 s, 1 GB.

When submitting on Luogu, please use a language version not lower than C++17, and you do not need to include the paint.h header file. However, you should add the following declarations:

void setting(int k, std::vector<int> p);
void alter(int t, int x, int y);

Problem Description

Little F learned how to draw trees in art class. He drew a tree $T$ with $n$ nodes, numbered from $1$ to $n$.

Since he is not satisfied with the current tree, Little F plans to modify it using $k$ pairs of pencils and erasers, where each pencil is paired one-to-one with an eraser. Initially, he places each pair of pencil and eraser on some node of the tree. Specifically, for $1 \le i \le k$, let the node where the pencil is located be $p_i$, and the node where the eraser is located be $e_i$. Initially, $p_i = e_i$. At any moment, multiple pencils and multiple erasers may be placed on the same node.

In each modification, Little F first chooses one pair of pencil and eraser. Suppose he chooses the $t$-th ($1 \le t \le k$) pair. Then he performs the modification as follows:

1. Choose any node $x$ ($1 \le x \le n$), move the pencil to node $x$, and draw the edge formed by the movement, i.e., add an edge between $p_t$ and $x$, then set $p_t \leftarrow x$.
2. Choose a node $y$ ($1 \le y \le n$) that is directly connected to $e_t$ by an edge (this edge may be the one newly drawn in the previous step), move the eraser to node $y$, and erase the edge passed through during the movement, i.e., delete the edge between $e_t$ and $y$, then set $e_t \leftarrow y$.

Of course, Little F must ensure that after each modification, the resulting graph is still a tree.

Little F hopes to use as few pencil-and-eraser pairs as possible to modify tree $T$ into another tree $T'$. You need to help Little F construct a set of modification plans. Specifically, you need to determine the number of pairs $k$, specify the initial position $p_i, e_i$ for each pair ($1 \le i \le k, p_i = e_i$), and then construct a sequence of modifications $(t, x, y)$ ($1 \le t \le k, 1 \le x, y \le n$), such that after performing these modifications in order, tree $T$ can be transformed into tree $T'$.

Implementation Details

Contestants do not need to, and should not, implement the main function.

Contestants need to ensure that the submitted program includes the header file paint.h, i.e., add the following code at the beginning of the program:

#include "paint.h"

Contestants need to implement the following two functions in the submitted source file paint.cpp:

void init(int c, int t);

• $c, t$ represent the test point number and the number of testdata groups, respectively. $c = 0$ means this test point is the sample.
• For each test point, this function will be called by the interactive library exactly once when the program starts running.

void paint(int n, std::vector<int> u, std::vector<int> v);

• $n$ is the number of nodes in tree $T$.
• For $0 \le i < n - 1$, $u_i, v_i$ represent an edge of tree $T$.
• For $n - 1 \le i < 2n - 2$, $u_i, v_i$ represent an edge of tree $T'$.
• For each test point, this function will be called by the interactive library exactly $t$ times.

Contestants can set the number of pencil-and-eraser pairs and the initial position of each pair by calling the following function:

void setting(int k, std::vector<int> p);

• $k$ is the number of pencil-and-eraser pairs used. Contestants must ensure $0 \le k \le 2n$.
• For $0 \le i < k$, $p_i$ is the initial position of the $(i+1)$-th pencil-and-eraser pair. Contestants must ensure that the length of $p$ is $k$, and for all $0 \le i < k$, $1 \le p_i \le n$.
• Contestants must ensure that each time the interactive library calls paint, this function is called exactly once.

Contestants can perform one modification by calling the following function:

void alter(int t, int x, int y);

• $t, x, y$ are the index of the chosen pencil-and-eraser pair and the node indices, respectively, with meanings as described in the Description. Contestants must ensure $1 \le t \le k$, $1 \le x, y \le n$, and that after the modification the resulting graph is still a tree.
• Contestants must ensure that each time the interactive library calls paint, the number of calls to this function does not exceed $10^5$, and all calls to this function occur after calling setting.

Note: In any case, the time required by the interactive library will not exceed $0.2$ seconds. Its memory usage is fixed-size and does not exceed $64$ MiB.

How to Run the Test Program

In the problem directory, grader.cpp is a reference implementation of the interactive library. The interactive library used in the final tests is different from this reference implementation, so contestants' solutions should not depend on the interactive library implementation.

You can compile an executable in this problem directory using the following command:

g++ grader.cpp paint.cpp -o paint -O2 -std=c++14 -static

Input Format

For the compiled executable program:

• The executable will read input from standard input in the following format:
  • The first line contains two non-negative integers $c, t$, representing the test point number and the number of testdata groups.
  • Then for each group of testdata, in order:
    • The first line contains a positive integer $n$, representing the number of nodes in tree $T$.
    • Line $i+1$ ($1 \le i \le n-1$) contains two positive integers $u_i, v_i$, representing an edge of tree $T$.
    • Line $i+n$ ($1 \le i \le n-1$) contains two positive integers $u'_i, v'_i$, representing an edge of tree $T'$.

Output Format

• The executable will output to standard output in the following format:
  • For each group of testdata:
    • The first line contains two non-negative integers $k, m$, representing the number of pencil-and-eraser pairs used and the length of the modification sequence.
    • The second line contains $k$ positive integers $p_1, p_2, \dots, p_k$, representing the initial positions of each pencil-and-eraser pair.
    • Line $i+2$ ($1 \le i \le m$) contains three positive integers $t, x, y$, representing, for the $i$-th modification, the index of the chosen pencil-and-eraser pair and the node indices.

0 2
5
2 3
3 1
5 1
5 4
1 4
2 3
3 1
5 3
5
4 2
1 3
5 1
1 2
2 1
3 5
3 1
4 5

1 3
1
1 4 5
1 5 4
1 3 5
2 2
4 5
1 5 2
2 3 1

Hint

Sample 1 Explanation

This sample contains two groups of testdata.

For the first group of testdata, tree $T$ contains edges $\{(1,3), (3,2), (1,5), (5,4)\}$, and tree $T'$ contains edges $\{(1,4), (2,3), (3,1), (5,3)\}$. One feasible modification plan is as follows:

• Initially, there is 1 pencil-and-eraser pair placed at node 1.
• In the first modification, choose $x = 4$, $y = 5$, add edge $(1,4)$, delete edge $(1,5)$. The resulting tree contains edges $\{(1,3), (3,2), (5,4), (1,4)\}$. At this time, $p_1 = 4$, $e_1 = 5$.
• In the second modification, choose $x = 5$, $y = 4$, add edge $(4,5)$, delete edge $(4,5)$. At this time, $p_1 = 5$, $e_1 = 4$.
• In the third modification, choose $x = 3$, $y = 5$, add edge $(5,3)$, delete edge $(4,5)$. The resulting tree contains edges $\{(1,3), (3,2), (1,4), (5,3)\}$, which is exactly tree $T'$.

Notes on the Provided Files

In this problem directory:

1. grader.cpp is the provided reference implementation of the interactive library.
2. paint.h is the header file; contestants do not need to care about its contents.
3. template_paint.cpp is the provided sample code; contestants may refer to it and implement their own code.

Contestants should back up all provided files. In the final evaluation, only paint.cpp in this problem directory will be tested, and modifications to files other than this program will not affect the evaluation result.

Constraints

For all testdata:

• $1 \le t \le 10$.
• $4 \le n \le 200$.
• For all $1 \le i < n$, $1 \le u_i, v_i \le n$, and all edges form a tree.
• For all $1 \le i < n$, $1 \le u'_i, v'_i \le n$, and all edges form a tree.
• Both $T$ and $T'$ are generated independently and uniformly at random among all trees on $n$ nodes.

::cute-table{tuack}

Scoring

Note:

• Contestants should not obtain internal information of the interactive library by illegal means, such as interacting directly with the standard input/output streams. Such behavior will be regarded as cheating.
• The interactive library used in the final evaluation is different from the sample interactive library implementation.

This problem is first subject to the same limits as traditional problems. For example, a compilation error will cause the whole problem to get $0$ points; a runtime error, exceeding the time limit, exceeding the memory limit, etc., will cause the corresponding test point to get $0$ points. Contestants may only access variables defined by themselves and variables provided by the interactive library. Attempting to access other address spaces may cause a compilation error or runtime error.

Each time the paint function is called, if the setting function or the alter function is called illegally, or the number of calls to alter exceeds $10^5$, then the corresponding test point gets $0$ points.

Based on the above conditions:

• In test points $1$ and $2$, the program gets full score if and only if, when each call to the paint function returns, tree $T$ has been transformed into tree $T'$.
• In test point $3$, for each group of testdata, let $k_{\min}$ be the minimum number of pencil-and-eraser pairs used.
  • If, when the paint function returns, tree $T$ has not been transformed into tree $T'$, then the score is $0$.
  • Otherwise, the score is $\lfloor 26 \cdot 0.97^{k - k_{\min}} \rfloor$.

The program's score is the minimum score over all testdata groups.

• In test point $4$, for each group of testdata, let $k_{\min}$ be the minimum number of pencil-and-eraser pairs used.
  • If $k \ne k_{\min}$, the score is $0$.
  • Otherwise, if, when the paint function returns, tree $T$ has not been transformed into tree $T'$, then the score is $4$.
  • Otherwise, the score is $\lfloor 4 + 33 \cdot 0.99^{\max(\lfloor m / 2000 \rfloor - 5, 0)} \rfloor$.

The program's score is the minimum score over all testdata groups.

Translated by ChatGPT 5