P17141 [NOI 2026] Teleport

The statement and sample attachments come from [QOJ](https://qoj.ac/contest/3938/problem/18984). When submitting to Luogu, there is no need to include the header `#include "teleport.h"`. Just copy ```cpp std::vector teleport(int c, int n, int m, std::vector u, std::vector v, std::vector x, std::vector y); ``` to the beginning of your program, and compile with a C++17 or higher compiler.

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

### 【Grader Program Mode】 You can compile an executable in this problem directory with the following command: ```bash 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/A

### 【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