#P18781. [2027年国家集训队互测]Another Story END
[2027年国家集训队互测]Another Story END
Another Story END
……除了一个圆满的结局,你还想要什么?
题目描述
给定一棵有 个结点的树,结点编号为 到 ,以结点 为根。对每个 ,结点 和其父亲 之间有一条双向边,颜色为 ,长度为 。
对树中出现过的一种颜色 ,如果一条简单路径经过了所有颜色为 的边,或者没有经过任何颜色为 的边,就称颜色 对该路径是好的;否则称它是坏的。
给定 ,求坏颜色数量不超过 的简单路径的最大长度。路径长度是所经边的长度之和。允许选择相同结点作为两个端点,此时不经过任何边,长度为 。
同一种颜色的边不一定连通,边长允许为 。
输入格式
第一行两个整数 。随后 行按照结点 的顺序,每行三个整数 ,描述该结点与父亲之间的边。
输出格式
输出一个整数,表示坏颜色数量不超过 的简单路径最大长度。
数据范围
,;每个 满足 、、。
样例
样例 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:每个 独立地从 等概率生成。
- D:对每种颜色,存在以结点1为一个端点的简单路径,包含该颜色全部边。