QOJ.ac

QOJ

実行時間制限: 2 s メモリ制限: 512 MB 満点: 100 ハック可能 ✓

#21438. Another Story END

統計

...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.

Discussions

About Discussions

The discussion section is only for posting: General Discussions (problem-solving strategies, alternative approaches), and Off-topic conversations.

This is NOT for reporting issues! If you want to report bugs or errors, please use the Issues section below.

Open Discussions 0
No discussions in this category.

Issues

About Issues

If you find any issues with the problem (statement, scoring, time/memory limits, test cases, etc.), you may submit an issue here. A problem moderator will review your issue.

Guidelines:

  1. This is not a place to publish discussions, editorials, or requests to debug your code. Issues are only visible to you and problem moderators.
  2. Do not submit duplicated issues.
  3. Issues must be filed in English or Chinese only.
Active Issues 0
No issues in this category.
Closed/Resolved Issues 0
No issues in this category.