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