Background

The statement and sample attachments come from QOJ.

When submitting to Luogu, there is no need to include the header #include "teleport.h". Just copy

std::vector<std::pair<long long, int>> teleport(int c, int n, int m, std::vector<int> u, std::vector<int> v, std::vector<int> x, std::vector<int> y);

to the beginning of your program, and compile with a C++17 or higher compiler.

Problem Description

Country $C$ has $n$ cities, numbered $0\sim n-1$. These $n$ cities are connected by $n-1$ roads, forming a tree structure. The $i$-th ($0\le i<n-1$) road connects cities $u_i$ and $v_i$, and it takes $1$ unit of time to travel from one endpoint city to the other.

To improve traffic efficiency, Country $C$ has developed a new type of teleport gate. Each city has one teleport gate. Using a teleport gate also takes $1$ unit of time, but since the system is not yet stable, it will teleport the user to one of all $n$ cities with equal probability. Note: using a teleport gate may also teleport you to the city you are currently in.

To test the effect of the teleport gates, Country $C$ conducted $m$ tests. In the $i$-th ($0\le i<m$) test, the tester is required to start from city $x_i$ and go to city $y_i$. During the trip from the start to the destination, the tester may choose to move along roads or use teleport gates. Since there are many possible ways to travel, the tester needs to find the travel strategy with the minimum expected time.

Specifically, define a travel strategy as follows: for every non-destination city, choose one adjacent city or choose to use the teleport gate. Every time the tester arrives at that city, they will move according to the pre-determined choice, i.e., move to the chosen adjacent city, or use the teleport gate.

Formally, a travel strategy can be represented by a sequence of length $n$, $[a_0,\ldots,a_{n-1}]$, where $a_{y_i}=-1$, and for all $j\ne y_i$, $a_j$ is adjacent to $j$, or $a_j=n$. Every time the tester arrives at city $j$ ($j\ne y_i$), if $a_j<n$, the tester moves to $a_j$; otherwise, the tester uses the teleport gate.

A travel strategy is called valid if and only if its expected time is finite.

For each test, compute the minimum expected time among all valid travel strategies.

【Implementation Details】

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

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

#include "teleport.h"

Contestants need to implement the following function in the submitted source file teleport.cpp:

std::vector<std::pair<long long, int>> teleport(int c, int n, int m, std::vector<int> u, std::vector<int> v, std::vector<int> x, std::vector<int> y);

• $c,n,m$ represent the test point index, the number of cities, and the number of tests, respectively. $c=0$ means this test point is the sample.
• $u,v$ represent the two cities connected by each road.
• $x,y$ represent the start and the destination of each test.
• This function needs to return a sequence of pairs of length exactly $m$: $(a_0,b_0),(a_1,b_1),\ldots,(a_{m-1},b_{m-1})$, where $a_i,b_i$ ($0\le i<m$) mean that, in the $i$-th test, the minimum expected time in lowest terms is $\frac{a_i}{b_i}$. In particular, if the minimum expected time is a positive integer, treat it as $b_i=1$.
• For each test point, this function will be called exactly once by the grader.

template_teleport.cpp in this problem directory is the provided sample code. You may refer to it and implement your own solution.

Input Format

【Grader Program Mode】

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

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

For the compiled executable teleport:

• The executable reads input from standard input in the following format:
  • The first line contains three non-negative integers $c,n,m$.
  • Line $i+2$ ($0\le i<n-1$) contains two non-negative integers $u_i,v_i$.
  • Line $i+n+1$ ($0\le i<m$) contains two non-negative integers $x_i,y_i$.
• The executable outputs to standard output in the following format:
  • Line $i+1$ ($0\le i<m$) contains two positive integers $a_i,b_i$.

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

7 3
1 1
2 1
1 1

Hint

【Sample $1$ Explanation】

For the $0$-th test:

• If the travel strategy is $[1,2,3,-1]$, then the time cost is the fixed value $3$.
• If the travel strategy is $[4,2,3,-1]$, then the tester will keep using the teleport gate until leaving city $0$, so the expected time is $\frac{7}{3}$.
• If the travel strategy is $[4,4,3,-1]$, then the tester will keep using the teleport gate until reaching city $2$ or city $3$, so the expected time is $3$.
• If the travel strategy is $[1,0,4,-1]$, then the tester will move forever between city $0$ and city $1$, so this travel strategy is not valid.

It can be proven that the minimum expected time is $\frac{7}{3}$.

【Sample $2$】

See teleport/teleport2.in and teleport/teleport2.ans in the contestant directory.

This sample satisfies the constraints of test points $2,3$.

【Sample $3$】

See teleport/teleport3.in and teleport/teleport3.ans in the contestant directory.

This sample satisfies the constraints of test points $4\sim6$.

【Sample $4$】

See teleport/teleport4.in and teleport/teleport4.ans in the contestant directory.

This sample satisfies the constraints of test points $7\sim8$.

【Sample $5$】

See teleport/teleport5.in and teleport/teleport5.ans in the contestant directory.

This sample satisfies the constraints of test point $9$.

【Sample $6$】

See teleport/teleport6.in and teleport/teleport6.ans in the contestant directory.

This sample satisfies the constraints of test point $16$.

【Sample $7$】

See teleport/teleport7.in and teleport/teleport7.ans in the contestant directory.

This sample satisfies the constraints of test points $17\sim20$.

【Constraints】

For all testdata:

• $2\le n\le5\times10^5$, $1\le m\le10^6$.
• For all $0\le i<n-1$, $0\le u_i,v_i<n$, and all $(u_i,v_i)$ form a tree.
• For all $0\le i<m$, $0\le x_i,y_i<n$ and $x_i\ne y_i$.

::cute-table{tuack} | Test Point Index | $n\le$ | $m\le$ | Special Property | |:-:|:-:|:-:|:-:| | $1$ | $4$ | $20$ | None | | $2,3$ | $5$ | $30$ | ^ | | $4\sim6$ | $10^2$ | $1$ | ^ | | $7,8$ | $10^3$ | $2000$ | $A$ | | $9$ | ^ | $10^6$ | None | | $10,11$ | $10^5$ | ^ | $A$ | | $12\sim15$ | ^ | ^ | None | | $16$ | $5\times10^5$ | $5\times10^5$ | $B$ | | $17\sim20$ | ^ | $10^6$ | None |

Special property $A$: For all $0\le i<n-1$, $u_i=i$ and $v_i=i+1$.

Special property $B$: For all $0\le i<m$, $y_i=0$.

Translated by ChatGPT 5