Description

Singapore’s Internet backbone consists of $n$ network sites, which are assigned indices from $0$ to $n-1$. The Internet also has $n-1$ bidirectional links, numbered from $0$ to $n-2$. Each link connects two different sites. Two sites connected by a link are called neighbors of each other.

A sequence of distinct sites $a_0,a_1,\ldots,a_p$ is called a path from site $x$ to site $y$ if and only if $a_0=x$, $a_p=y$, and every two consecutive sites in the sequence are neighbors. It is guaranteed that for any site $x$ and any other site $y$, there exists exactly one path.

Any site $x$ can generate a packet and send it to any other site $y$, where site $y$ is called the packet’s destination site. The packet must be routed along the unique path from site $x$ to site $y$ according to the following rules. Suppose the packet has currently arrived at site $z$, where $y$ is the destination and $z \ne y$. Then site $z$ will:

1. Execute the routing function to find the neighbor of $z$ that lies on the unique path from $z$ to $y$. Then
2. Forward the packet to that neighbor.

However, sites have limited storage memory and may not be able to store the full list of backbone links needed by the routing function.

Your task is to implement the routing mechanism of the backbone, which consists of two functions.

• The first function takes as input $n$, the list of backbone links, and an integer $k \ge n-1$. This function must assign each site a unique label, with values between $0$ and $k$ (inclusive).
• The second function is the routing function. After the labels are assigned, it is deployed on all sites. Its input parameters are:
  • $s$, the label of the site where the packet is currently located,
  • $t$, the label of the destination site $(t \ne s)$,
  • $c$, the list of labels of all neighboring sites of $s$.

This function should return the label of a neighbor of $s$, indicating the next site to which the packet should be forwarded.

In each subtask, your score depends on the maximum label assigned among all sites (in general, the smaller the maximum label, the better).

Implementation Details

You need to implement the following functions:

int[] label(int n, int k, int[] u, int[] v)

• $n$: the number of sites in the backbone.
• $k$: the maximum available label value.
• $u$ and $v$: arrays of size $n-1$ describing the links. For each $i(0 \le i \le n-2)$, link $i$ connects the sites with indices $u[i]$ and $v[i]$.
• This function should return an array $L$ of size $n$. For each $i(0 \le i \le n-1)$, $L[i]$ is the label assigned to the site with index $i$. All elements of $L$ must be pairwise distinct and between $0$ and $k$ (inclusive).

int find_next_station(int s, int t, int[] c)

• $s$: the label of the site where the packet is currently located.
• $t$: the label of the destination site.
• $c$: an array containing the labels of all neighbors of $s$. The array $c$ is sorted in increasing order.
• This function should return the label of a neighbor of $s$, indicating the next site to which the packet should be forwarded.

Each test case contains one or more independent scenarios (i.e., different backbone descriptions). For a test case containing $r$ scenarios, the grader will run the above functions exactly twice, following the steps below.

During the first run:

• The label function is called $r$ times.
• The returned labels are saved by the grading system.
• find_next_station is not called.

During the second run:

• find_next_station is called multiple times. For each call, the grader chooses an arbitrary scenario, and the labeling returned by the label function for that scenario is used for this find_next_station call.
• label is not called.
• In particular, any information stored in static or global variables during the first run of the grader cannot be used in the find_next_station function.

Input Format

Output Format

Hint

Sample Explanation

Example 1

Consider the following call:

label(5, 10, [0, 1, 1, 2], [1, 2, 3, 4])

There are $5$ sites and $4$ links. The pairs of site indices for the links are $(0,1)$, $(1,2)$, $(1,3)$, and $(2,4)$. The labels range from $0$ to $k=10$.

To return the following labeling scheme:

the function label should return $[6,2,9,3,7]$. The numbers in the figure below show the site indices (left) and the assigned labels (right).

Assume the labels are assigned as shown above, and consider the following call:

find_next_station(9, 6, [2, 7])

This means the packet is currently at the site with label $9$, and its destination site has label $6$. Along the path from the current site to the destination site, the site labels are $[9,2,6]$. Therefore, the function should return $2$, indicating that the packet should be forwarded to the site with label $2$ (whose index is $1$).

Consider another possible call:

find_next_station(2, 3, [3, 6, 9])

This function should return $3$, because the destination site (label $3$) is a neighbor of the current site (label $2$), so the destination site directly receives the packet.

Constraints

• $1 \le r \le 10$

For each call to label:

• $2 \le n \le 1000$
• $k \ge n-1$
• $0 \le u[i],v[i] \le n-1$（for all $0 \le i \le n-2$）

For each call to find_next_station, its input parameters come from labels produced by some previously chosen call to label. With respect to the produced labels:

• $s$ and $t$ are the labels of two different sites.
• $c$ is the sequence of labels of all neighbors of the site with label $s$, sorted in increasing order.

For each test case, across all scenarios combined, the total length of all arrays $c$ passed to the function find_next_station does not exceed $10^5$.

Subtasks

1. (5 points) $k=1000$, no site will have more than $2$ neighbors.
2. (8 points) $k=1000$, link $i$ connects sites $i+1$ and $\lfloor\frac{i}{2}\rfloor$.
3. (16 points) $k=10^6$, at most one site has more than $2$ neighbors.
4. (10 points) $n \le 8$, $k = 10^9$
5. (61 points) $k = 10^9$

In subtask 5, you can receive partial credit. Let $m$ be the maximum label returned by label across all scenarios. For this subtask, your score is computed according to the table below:

Sample Grader

The sample grader reads the input data in the following format:

Line $1$: $r$

Then follow $r$ blocks, each describing one scenario, in the following format:

Line $1$: $n\ k$
Lines $2+i(0 \le i \le n-2)$: $u[i]\ v[i]$
Line $1+n$: $q$, the number of calls to find_next_station
Lines $2+n+j(0 \le j \le q-1)$: $z[j]\ y[j]\ w[j]$, the indices of the sites involved in the $j$-th call to find_next_station. At this time, the packet is at site $z[j]$, the destination site is $y[j]$, and it should be forwarded to site $w[j]$.

The sample grader prints your output in the following format:

Line $1$: $m$

Then follow $r$ blocks corresponding to the scenarios in the input. Each block has the following format:

Lines $1+j(0 \le j \le q-1)$: a site index, whose corresponding label is the result returned by the $j$-th call to find_next_station.

Note: each time the sample grader is executed, it calls both label and find_next_station.

Translated by ChatGPT 5