Problem Description

You hired an assistant with the profit from your vending robots, and now you are ready to take the safe containing the CEOI medals.

The safe is located in a university building consisting of $n$ rooms, connected by $n-1$ doors. Every room is reachable from any other room, and each room is connected to at most $3$ doors.
Both you and your assistant have a floor plan describing how the rooms are connected, but although your two plans describe the same structure, the numbering of rooms and doors may be different.

On the second day of the contest, the committee is busy handling announcements and contestants' questions. This will be a perfect chance to get close to the safe with the medals.

Your assistant will first search the whole building. Once he finds the room containing the safe, he will leave you hints on how to get to that room. Since phones cannot be brought into the contest area, he uses an almost unlimited supply of identical ties left over from last year's BOI. Because these ties are indistinguishable, the only information you can obtain is the number of ties he left in any given room. Since too many ties in one room would be very suspicious, the maximum number of ties in any single room should be as small as possible (see the scoring section).

After that, you plan to sneak out while going to the bathroom, and use the ties your assistant left to find the room with the safe. The safe is hidden in a room, so when you enter the room containing the safe, you must be able to identify that room using only the ties; moreover, since staying “in the bathroom” for too long would be noticed, you must find the safe as quickly as possible. You may traverse at most $d+30$ doors, where $d$ is the number of doors on the shortest path from your initial position to the safe. If you traverse the same door multiple times, each traversal is counted.

Therefore, you need to write a program that tells your assistant how many ties to leave in each room, and guides you to the room containing the safe.

Input Format

This is an interactive function problem.

For each test case, your program will be run twice.

You need to implement the following two functions (function prototypes are given):

vector<int> mark(vector<pair<int,int>> F, int safe);

• $F$: contains $n-1$ pairs $(u,v)$, where $1 \le u,v \le n$ and it is guaranteed that $u \neq v$, meaning that on your assistant's map, room $u$ and room $v$ are connected by a door.
• $\mathrm{safe}$: the room number of the safe on your assistant's map.

This function should return a vector<int> $v$ of length $n$, where each element $v_i$ is the number of ties your assistant should leave in room $i+1$ on his map. You should guarantee $0 \le v_i \le 10^9$.

void locate(vector<pair<int,int>> F,int curr,int t);

• $F$: contains $n-1$ pairs $(u,v)$, where $1 \le u,v \le n$ and it is guaranteed that $u \neq v$, meaning that on your map, room $u$ and room $v$ are connected by a door.
• $\mathrm{curr}$: the room number where you are currently located.
• $t$: the number of ties found in the room you are currently in.

In the description below, room numbers follow your map's numbering.

While implementing the function locate, you may call the following function:

int visit(int v);

to move from your current room $u$ to an adjacent room $v$. You must ensure the operation is legal, i.e. $1 \le v \le n,(u,v) \in F\:\vee (v,u) \in F$.

This function returns a non-negative integer $k$, meaning the number of ties you find in room $v$.

The number of calls to this function must not exceed $d+30$, where $d$ is the shortest distance from your start to your destination.

When the function locate terminates, you should be in the room containing the safe.

For each test case, in the first run the program calls mark, and in the second run it calls locate.

If visit is called too many times, called illegally, or called in mark, your program will be terminated and the submission will be judged Wrong Answer.
Your program must not read from or write to stdin or stdout, otherwise it will be judged Security Violation.
However, you may print anything to stderr.

You need to add #include "incursion.h" at the beginning of your source code file.

You should link your program with sample_grader.cpp for local testing.

Below is an explanation of the sample grader. Please refer to sample_grader.cpp for the operation details.

For simplicity, this grader will not run your program twice; instead, in a single run it calls each of the two functions once. The attachment contains an example implementation of sample_grader.cpp.

Note: this implementation is not the same as the one used in the actual judging. It is forbidden to try to pass this task by hacking the grader.

Hint

Scoring Rules

There are 4 subtasks. For each test case, $2 \le n \le 45000$.

Subtask 1 (30 points): it is guaranteed that no room is connected to $3$ doors. Subtask 2 (30 points): there is exactly one room connected to $2$ doors. Subtask 3 (40 points): no special properties.

For each test case, suppose the room using the most ties uses $T_{\max}$ ties:

• If $T_{\max}<2$, you will get $100\%$ of the score for that test case.
• If $T_{\max}=2$, you will get $40\%$ of the score for that test case.
• If $2 < T_{\max} \le 10^9$, you will get $30\%$ of the score for that test case.

How to Use the Interactive Library

Note: the interactive library provided by Luogu is different from the original one.

Compile with g++ -std=c++17 -Wall -O2 -o test interactive_lib.cpp xxx.cpp, where xxx.cpp is the name of your program.

The sample interactive library first reads three positive integers $n$, $s$, $seed$ from standard input, meaning the number of nodes, the original index of the starting point, and the random seed.

Then it reads $n-1$ lines, each with two positive integers $u,v$, representing an edge of the original tree. It is guaranteed that $1 \le u < v \le n$.
Then it reads one line containing a string, representing the shuffling rule.

You do not need to care about the exact implementation of the shuffling. This implementation may not be the same as the one used in the final judging.

Next, the interactive library will call mark once and locate once. Note that the interactive library may shuffle the numbering.

The interactive library may output the following information to the terminal:

• Invalid input. The input is invalid.
• Invalid call to visit. (ALICE CALLED VISIT) visit was called in mark.
• Invalid call to visit. (INDEX ERROR) An invalid node was visited.
• Invalid call to visit. (NOT CONNECTED) The visited node is not directly connected to the current node by an edge.
• Invalid call to visit. (TOO MANY VISITS) visit was called too many times.
• Invalid return value of mark. The return value of mark is invalid, i.e. the returned vector does not have length $n$, or contains a number less than $0$ or greater than $10^9$.
• Not correct: current position is X You did not end at the target node; you should be at node $X$ (on the second map).
• Correct: at most X tie(s) per room. You reached the target node, and the maximum number of ties used in any room is $X$.

In the final judging, only whether it is correct or not will be reported.

Translated by ChatGPT 5