P8934 [JRKSJ R7] TSM eerT

对于一个 $n$ 个结点的带边权的树 $T$，定义 $dis(x,y)$ 为 $T$ 中 $x\to y$ 路径上的边权和。再定义一个 $n$ 个结点的无向完全图 $p(T)=G$，其中 $\forall x,y\in [1,n]$，$G$ 中边 $(x,y)$ 的边权为 $dis(x,y)$。 定义 $f(T)$ 为 $p(T)$ 的最大生成树。特别的，若 $p(T)$ 的最大生成树不唯一，请立刻判断出并报告。 给定树 $T_0$ 和整数 $k$，求 $f^k(T_0)$。其定义将在下文给出。

无

无

### 定义 $f^k(T)$ 的定义为： $$f^k(T)=\begin{cases}T&k=0\\f(f^{k-1}(T))&k>0\end{cases}$$ ### 样例 $1$ 解释  分别是 $T_0,f(T_0),f^2(T_0),f^3(T_0)$。 以计算 $f(T_0)$ 的过程为例，生成的 $p(T_0)=G$ 为  最大生成树上的边为 $(1,3),(2,3)$。 ### 数据规模 本题采用捆绑测试。 | $\text{Subtask}$ | $n\le$ | $k\le$ | $\text{Score}$ | | :----------: | :----------: | :----------: | :----------: | | $1$ | $10^3$ | $1$ | $10$ | | $2$ | $10^5$ | $1$ |$20$ | | $3$ | $10^6$ | $1$ |$30$ | | $4$ | $10^6$ | $10^7$ |$40$ | 对于 $100\%$ 的数据，$2\le n\le 10^6$，$1\le k\le 10^7$，$1\le f_i