Problem Description

For a tree \( T \) with \( n \) nodes and edge weights, define \( dis(x, y) \) as the sum of edge weights on the path from \( x \) to \( y \) in \( T \). Define a complete undirected graph \( p(T) = G \) with \( n \) nodes, where for all \( x, y \in [1, n] \), the edge weight of edge \( (x, y) \) in \( G \) is \( dis(x, y) \).

Define \( f(T) \) as the maximum spanning tree of \( p(T) \). If the maximum spanning tree of \( p(T) \) is not unique, immediately identify and report it.

Given a tree \( T_0 \) and an integer \( k \), find \( f^k(T_0) \). Its definition will be provided below.

Input Format

The first line contains two integers \( n \) and \( k \).
The next \( n-1 \) lines, each containing two integers \( i-f_i \) and \( v_i \), represent an edge \( (i, f_i) \) in \( T_0 \) with edge weight \( v_i \). This means the input line contains two integers \( f'_i \) and \( v_i \), where the actual \( f_i = i - f'_i \).

Output Format

Output a single integer as the answer.

If there 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} \).

Sample Input and Output

Sample Input #1

3 3
1 1
2 2

Sample Output #1

13

Sample Input #2

10 2
1 7
1 2
1 5
4 5
2 1
3 9
2 9
4 4
9 4

Sample Output #2

736

Sample Input #3

4 1
1 1
2 1
3 1

Sample Output #3

-1

Notes

Definition

The definition of \( f^k(T) \) is:
\[ f^k(T) = \begin{cases} T & \text{if } k = 0 \\ f(f^{k-1}(T)) & \text{if } k > 0 \end{cases} \]

Sample #1 Explanation

These are \( T_0, f(T_0), f^2(T_0), f^3(T_0) \).

Taking the calculation of \( 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) \).

Data Size

This problem uses bundled testing.

For 100% of the data, \( 2 \le n \le 10^6 \), \( 1 \le k \le 10^7 \), \( 1 \le f_i < i \), \( 1 \le v_i \le 10^9 \).

Special Scoring Method

This problem has subtask dependencies, specifically:
- For subtask \( i \), you need to correctly solve all subtasks \( j \) where \( j \in [1, i] \) to earn the score for subtask \( i \).

见题面 Input 部分

见题面 Output 部分