luogu#P9047. [PA2021] Poborcy podatkowi
[PA2021] Poborcy podatkowi
题目描述
给定一棵 个点的树,你可以选择若干条长度为 的不相交链(可以不选)。
每个选链的方案的收益为所选链的并集的边权和,求最大收益。
输入格式
第一行,一个整数 ;
接下来 行,每行三个整数 ,表示树上的一条边 ,其边权为 。
输出格式
一行,一个整数,表示所求的值。
19
1 2 1
2 3 2
3 4 -1
4 5 -1
5 6 2
6 7 11
7 8 12
8 9 13
9 10 14
11 12 3
12 13 0
13 14 0
14 15 0
15 16 1
16 4 0
4 17 0
17 18 0
18 19 2
57
6
1 2 2
2 3 -1
3 4 -1
4 5 -1
5 6 2
0
提示
样例 #1 解释
给出一种最优方案:选择链 ,,,。
样例 #2 解释
由于每一条长度为 的链权值均为负数,所以不选最优。
数据范围
对于 的数据,,。