#PQJ4621x21438. QOJ 4621_21438

    ID: 2978 传统题 2000ms 512MiB 尝试: 0 已通过: 0 难度: NOI/NOI+/CTS 上传者: 标签>来源:qoj.ac章节练习数据:双算对拍权威答案来源:集训队赛事:IOI 2027 互测树上算法深搜

QOJ 4621_21438

标题: Another Story END - Problem - QOJ.ac

Statistics

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

题目描述

给定一棵有 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 为端点的简单路径,包含该颜色的全部边。