P17141 [NOI 2026] 传送

题面、样例附件来自 [QOJ](https://qoj.ac/contest/3938/problem/18984)。 提交到洛谷上时，无需引用头文件 `#include "teleport.h"`。直接将 ```cpp std::vector teleport(int c, int n, int m, std::vector u, std::vector v, std::vector x, std::vector y); ``` 复制到程序开头，同时选用 C++17 或者更高版本编译器编译。

$C$ 国共有 $n$ 座城市，编号为 $0\sim n-1$。这 $n$ 座城市由 $n-1$ 条道路连接，形成树形结构。第 $i$（$0\le i

### 【测试程序方式】 选手可以在本题目录下使用如下命令编译得到可执行文件： ```bash g++ grader.cpp teleport.cpp -o teleport -O2 -std=c++14 -static ``` 对于编译得到的可执行文件 `teleport`： - 可执行文件将从标准输入读入以下格式的数据： - 第一行包含三个非负整数 $c,n,m$。 - 第 $i+2$（$0\le i

无

### 【样例 $1$ 解释】 对于第 $0$ 次测试： - 若通行方式为 $[1,2,3,-1]$，则耗时为固定值 $3$。 - 若通行方式为 $[4,2,3,-1]$，则测试员将不断使用传送门直至离开城市 $0$，因此期望耗时为 $\frac{7}{3}$。 - 若通行方式为 $[4,4,3,-1]$，则测试员将不断使用传送门直至到达城市 $2$ 或城市 $3$，因此期望耗时为 $3$。 - 若通行方式为 $[1,0,4,-1]$，则测试员将永远在城市 $0$ 与城市 $1$ 间移动，因此该通行方式不是合理的。 可以证明，期望耗时的最小值为 $\frac{7}{3}$。 ### 【样例 $2$】 见选手目录下的 `teleport/teleport2.in` 与 `teleport/teleport2.ans`。 该样例满足测试点 $2,3$ 的约束条件。 ### 【样例 $3$】 见选手目录下的 `teleport/teleport3.in` 与 `teleport/teleport3.ans`。 该样例满足测试点 $4\sim6$ 的约束条件。 ### 【样例 $4$】 见选手目录下的 `teleport/teleport4.in` 与 `teleport/teleport4.ans`。 该样例满足测试点 $7\sim8$ 的约束条件。 ### 【样例 $5$】 见选手目录下的 `teleport/teleport5.in` 与 `teleport/teleport5.ans`。 该样例满足测试点 $9$ 的约束条件。 ### 【样例 $6$】 见选手目录下的 `teleport/teleport6.in` 与 `teleport/teleport6.ans`。 该样例满足测试点 $16$ 的约束条件。 ### 【样例 $7$】 见选手目录下的 `teleport/teleport7.in` 与 `teleport/teleport7.ans`。 该样例满足测试点 $17\sim20$ 的约束条件。 ### 【数据范围】 对于所有测试数据，均有： - $2\le n\le5\times10^5$，$1\le m\le10^6$； - 对于所有 $0\le i