...What else could you wish for, other than a happy ending?
You are given a tree with $n$ vertices numbered from $1$ to $n$, rooted at vertex $1$. For each $i = 2, 3, \ldots, n$, there is an undirected edge between vertex $i$ and its parent $p_i$ with color $c_i$ and length $w_i$.
For a color $c$ that appears in the tree, if a simple path passes through all edges of color $c$, or does not pass through any edge of color $c$, then color $c$ is said to be good for this path; otherwise, color $c$ is said to be bad for this path.
Given an integer $k \in \{0, 1\}$, find the maximum length of a simple path with at most $k$ bad colors. The length of a path is defined as the sum of the lengths of all edges on the path.
You may choose the same vertex as both endpoints of the path; in this case, the path passes through no edges and has length $0$.
Note that edges of the same color do not necessarily form a connected subgraph, and edge lengths can be $0$.
Input
The first line contains two integers $n, k$, representing the number of vertices and the maximum allowed number of bad colors, respectively.
The $i$-th of the next $n - 1$ lines contains three integers $p_i, c_i, w_i$, indicating that there is an undirected edge between vertex $i$ and vertex $p_i$ with color $c_i$ and length $w_i$.
Output
Output a single line containing an integer, representing the maximum length of a simple path with at most $k$ bad colors.
Examples
Input 1
6 1 1 1 1 1 1 4 1 2 2 1 2 8 1 3 100
Output 1
108
Note
Choose the path from vertex $5$ to vertex $6$, passing through vertices $5, 1, 6$ in order, with length $8 + 100 = 108$.
This path passes through no edges of color $1$ and all edges of color $3$, so colors $1, 3$ are both good. It passes through only one of the two edges of color $2$, so color $2$ is bad.
This path has exactly one bad color, which satisfies the condition. It can be proven that no longer valid path exists.
Input 2
10 0 1 1 3 1 2 4 2 1 5 2 3 40 3 2 6 3 4 2 4 5 8 6 5 9 7 3 10
Output 2
35
Note
Choose the path from vertex $8$ to vertex $9$, passing through vertices $8, 4, 2, 1, 3, 6, 9$ in order, with length $8 + 5 + 3 + 4 + 6 + 9 = 35$.
This path passes through all edges of colors $1, 2, 5$ and no edges of colors $3, 4$, so there are no bad colors, which satisfies the condition. It can be proven that no longer valid path exists.
Input 3
10 1 1 1 6 1 1 5 1 1 0 1 2 8 1 2 0 2 3 2 3 4 3 5 5 1 6 6 4
Output 3
16
Note
Choose the path from vertex $7$ to vertex $8$, passing through vertices $7, 2, 1, 3, 8$ in order, with length $2 + 6 + 5 + 3 = 16$.
This path passes through two of the three edges of color $1$, so color $1$ is bad. It passes through all edges of colors $3, 4$ and no edges of any other color, so it has exactly one bad color, which satisfies the condition.
The path from vertex $7$ to vertex $9$ has length $17$, but colors $1, 2$ are both bad, which does not satisfy the condition. It can be proven that no valid path of length greater than $16$ exists.
Constraints
For all test data, it is guaranteed that:
- $2 \le n \le 2 \times 10^5$;
- $k \in \{0, 1\}$;
- For each $i = 2, 3, \ldots, n$, $1 \le p_i < i$, $1 \le c_i \le n$, and $0 \le w_i \le 10^9$.
Subtasks
This problem uses bundled testing with reasonable subtask dependencies.
| Subtask | $n \le$ | $k =$ | Special Property | Score |
|---|---|---|---|---|
| $1$ | $200$ | $0$ or $1$ | None | $5$ |
| $2$ | $3000$ | $0$ or $1$ | None | $9$ |
| $3$ | $2 \times 10^5$ | $0$ | A | $4$ |
| $4$ | $2 \times 10^5$ | $0$ | B | $5$ |
| $5$ | $2 \times 10^5$ | $0$ | C | $3$ |
| $6$ | $2 \times 10^5$ | $0$ | D | $4$ |
| $7$ | $2 \times 10^5$ | $0$ | None | $7$ |
| $8$ | $2 \times 10^5$ | $1$ | A | $8$ |
| $9$ | $2 \times 10^5$ | $1$ | B | $14$ |
| $10$ | $2 \times 10^5$ | $1$ | C | $9$ |
| $11$ | $2 \times 10^5$ | $1$ | D | $8$ |
| $12$ | $10^5$ | $1$ | None | $11$ |
| $13$ | $2 \times 10^5$ | $1$ | None | $13$ |
- Special Property A: For each color, all edges of this color form a connected subgraph.
- Special Property B: Each color appears at most twice.
- Special Property C: For each $i = 2, 3, \ldots, n$, $p_i$ is chosen independently and uniformly at random from the integers $1, 2, \ldots, i - 1$.
- Special Property D: For each color, there exists a simple path with vertex $1$ as one of its endpoints that contains all edges of this color.