QOJ.ac

QOJ

時間限制: 2 s 記憶體限制: 512 MB 總分: 100 可 Hack ✓

#21438. Another Story END

统计

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

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

Discussions

About Discussions

The discussion section is only for posting: General Discussions (problem-solving strategies, alternative approaches), and Off-topic conversations.

This is NOT for reporting issues! If you want to report bugs or errors, please use the Issues section below.

Open Discussions 0
No discussions in this category.

Issues

About Issues

If you find any issues with the problem (statement, scoring, time/memory limits, test cases, etc.), you may submit an issue here. A problem moderator will review your issue.

Guidelines:

  1. This is not a place to publish discussions, editorials, or requests to debug your code. Issues are only visible to you and problem moderators.
  2. Do not submit duplicated issues.
  3. Issues must be filed in English or Chinese only.
Active Issues 0
No issues in this category.
Closed/Resolved Issues 0
No issues in this category.