P8934 [JRKSJ R7] TSM eerT

For a weighted tree $T$ with $n$ nodes, define $dis(x,y)$ as the sum of edge weights on the path $x\to y$ in $T$. Then define an undirected complete graph $p(T)=G$ with $n$ nodes, where for all $x,y\in [1,n]$, the weight of edge $(x,y)$ in $G$ is $dis(x,y)$. Define $f(T)$ as the maximum spanning tree of $p(T)$. In particular, if the maximum spanning tree of $p(T)$ is not unique, you must determine it immediately and report it. Given a tree $T_0$ and an integer $k$, find $f^k(T_0)$. Its definition is given below.

The first line contains two integers $n,k$.\ In the next lines $2\sim n$, line $i$ contains two integers $i-f_i,v_i$, representing an edge $(i,f_i)$ of $T_0$ with weight $v_i$. **That is, this line inputs two integers $f'_i,v_i$, and the real $f_i=i-f'_i$.**

Output only one integer as the answer. If $\exists x\in[0,k-1]$ such that the maximum spanning tree of $p(f^x(T_0))$ is not unique, output $-1$. Otherwise, output the sum of all edge weights of $f^k(T_0)$ modulo $2^{32}$.

### Definition The definition of $f^k(T)$ is: $$f^k(T)=\begin{cases}T&k=0\\f(f^{k-1}(T))&k>0\end{cases}$$ ### Explanation for Sample $1$  They are $T_0,f(T_0),f^2(T_0),f^3(T_0)$. Take the process of computing $f(T_0)$ as an example. The generated $p(T_0)=G$ is  The edges in the maximum spanning tree are $(1,3),(2,3)$. ### Constraints This problem uses bundled testdata. | $\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$ | For $100\%$ of the data, $2\le n\le 10^6$, $1\le k\le 10^7$, $1\le f_i