……除了一个圆满的结局,你还想要什么?
给定一棵有 $n$ 个结点的树,结点编号从 $1$ 到 $n$,以结点 $1$ 为根。对于每个 $i = 2, 3, \ldots, n$,结点 $i$ 与其父亲 $p_i$ 之间有一条双向边,这条边的颜色为 $c_i$,长度为 $w_i$。
对于树中出现过的一种颜色 $c$,如果一条简单路径经过了所有颜色为 $c$ 的边,或者没有经过任何颜色为 $c$ 的边,就称颜色 $c$ 对这条路径是好的;否则,称颜色 $c$ 对这条路径是坏的。
给定一个整数 $k \in \{0, 1\}$,请你求出坏颜色数量不超过 $k$ 的简单路径的最大长度。路径的长度定义为路径上所有边的长度之和。
你可以选择相同的结点作为路径的两个端点,此时路径不经过任何边,长度为 $0$。
请注意,同一种颜色的边不一定连通,边的长度可以为 $0$。
输入格式
第一行包含两个整数 $n, k$,分别表示结点数量和允许的坏颜色数量上限。
接下来 $n - 1$ 行的第 $i$ 行包含三个整数 $p_i, c_i, w_i$,表示结点 $i$ 与结点 $p_i$ 之间有一条颜色为 $c_i$、长度为 $w_i$ 的双向边。
输出格式
输出一行一个整数,表示坏颜色数量不超过 $k$ 的简单路径的最大长度。
样例
输入格式 1
6 1 1 1 1 1 1 4 1 2 2 1 2 8 1 3 100
输出格式 1
108
说明
选择从结点 $5$ 到结点 $6$ 的路径,依次经过结点 $5, 1, 6$,长度为 $8 + 100 = 108$。
这条路径没有经过颜色为 $1$ 的边,经过了全部颜色为 $3$ 的边,因此颜色 $1, 3$ 都是好的。它只经过了两条颜色为 $2$ 的边中的一条,因此颜色 $2$ 是坏的。
这条路径恰有一种坏颜色,满足要求,可以证明不存在更长的合法路径。
输入格式 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
输出格式 2
35
说明
选择从结点 $8$ 到结点 $9$ 的路径,依次经过结点 $8, 4, 2, 1, 3, 6, 9$,长度为 $8 + 5 + 3 + 4 + 6 + 9 = 35$。
这条路径经过了颜色 $1, 2, 5$ 的全部边,没有经过颜色 $3, 4$ 的任何边,因此没有坏颜色,满足要求,可以证明不存在更长的合法路径。
输入格式 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
输出格式 3
16
说明
选择从节点 $7$ 到节点 $8$ 的路径,依次经过节点 $7, 2, 1, 3, 8$,长度为 $2 + 6 + 5 + 3 = 16$。
这条路径经过了颜色 $1$ 的三条边中的两条,因此颜色 $1$ 是坏的。它经过了颜色 $3, 4$ 的全部边,没有经过其他颜色的任何边,因此恰有一种坏颜色,满足要求。
从节点 $7$ 到节点 $9$ 的路径长度为 $17$,但颜色 $1, 2$ 都是坏的,不满足要求。可以证明不存在长度超过 $16$ 的合法路径。
数据范围
对于所有数据,满足:
- $2 \le n \le 2 \times 10^5$;
- $k \in \{0, 1\}$;
- 对于每个 $i = 2, 3, \ldots, n$,有 $1 \le p_i < i$、$1 \le c_i \le n$、$0 \le w_i \le 10^9$。
子任务
本题采用捆绑测试,且开启了合理的子任务依赖。
| 子任务编号 | $n \le$ | $k =$ | 特殊性质 | 分值 |
|---|---|---|---|---|
| $1$ | $200$ | $0$ 或 $1$ | 无 | $5$ |
| $2$ | $3000$ | $0$ 或 $1$ | 无 | $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$ | 无 | $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$ | 无 | $11$ |
| $13$ | $2 \times 10^5$ | $1$ | 无 | $13$ |
- 特殊性质 A:对于每种颜色,该颜色的全部边构成连通子图。
- 特殊性质 B:每种颜色至多出现两次。
- 特殊性质 C:对于每个 $i = 2, 3, \ldots, n$,$p_i$ 独立地从整数 $1, 2, \ldots, i - 1$ 中等概率随机生成。
- 特殊性质 D:对于每种颜色,存在一条以结点 $1$ 为端点的简单路径,包含该颜色的全部边。