#P18781. [2027年国家集训队互测]Another Story END

[2027年国家集训队互测]Another Story END

Another Story END

……除了一个圆满的结局,你还想要什么?

题目描述

给定一棵有 nn 个结点的树,结点编号为 11 到 nn,以结点 11 为根。对每个 i=2,3,…,ni=2,3,\ldots,n,结点 ii 和其父亲 pip_i 之间有一条双向边,颜色为 cic_i,长度为 wiw_i。

对树中出现过的一种颜色 cc,如果一条简单路径经过了所有颜色为 cc 的边,或者没有经过任何颜色为 cc 的边,就称颜色 cc 对该路径是好的;否则称它是坏的。

给定 k∈{0,1}k\in\{0,1\},求坏颜色数量不超过 kk 的简单路径的最大长度。路径长度是所经边的长度之和。允许选择相同结点作为两个端点,此时不经过任何边,长度为 00。

同一种颜色的边不一定连通,边长允许为 00。

输入格式

第一行两个整数 n,kn,k。随后 n−1n-1 行按照结点 i=2,3,…,ni=2,3,\ldots,n 的顺序,每行三个整数 pi,ci,wip_i,c_i,w_i,描述该结点与父亲之间的边。

输出格式

输出一个整数,表示坏颜色数量不超过 kk 的简单路径最大长度。

数据范围

2≤n≤2000002\le n\le200000,k∈{0,1}k\in\{0,1\};每个 i=2,…,ni=2,\ldots,n 满足 1≤pi<i1\le p_i<i、1≤ci≤n1\le c_i\le n、0≤wi≤1090\le w_i\le10^9。

样例

样例 1 输入

6 1
1 1 1
1 1 4
1 2 2
1 2 8
1 3 100

样例 1 输出

108

选择5→1→6,长8+100=108。颜色1未出现,颜色3全部出现,均好;颜色2只出现两条中的一条,坏色恰为1个。

样例 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→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→2→1→3→8,长2+6+5+3=16。颜色1出现三条中的两条,颜色3、4全部出现,其余颜色未出现,恰有1个坏色。7到9虽长17,但颜色1、2都坏,不合法。上述路径分别达到最优。

数据分组参考

下表列出数据分组性质。当前评测采用50个测试点,每点2分。

子任务 n上限 k 特殊性质 分值
1 200 0或1 无 5
2 3000 9
3 200000 0 A 4
4 B 5
5 C 3
6 D 4
7 无 7
8 1 A 8
9 B 14
10 C 9
11 D 8
12 100000 无 11
13 200000 13
  • A:每种颜色的全部边构成连通子图。
  • B:每种颜色至多出现两次。
  • C:每个 pip_i 独立地从 1,2,…,i−11,2,\ldots,i-1 等概率生成。
  • D:对每种颜色,存在以结点1为一个端点的简单路径,包含该颜色全部边。

样例附件