luogu#P9047. [PA2021] Poborcy podatkowi

[PA2021] Poborcy podatkowi

题目描述

给定一棵 nn 个点的树,你可以选择若干条长度为 44 的不相交链(可以不选)。

每个选链的方案的收益为所选链的并集的边权和,求最大收益。

输入格式

第一行,一个整数 nn

接下来 n1n - 1 行,每行三个整数 u,v,wu, v, w,表示树上的一条边 (u,v)(u, v),其边权为 ww

输出格式

一行,一个整数,表示所求的值。

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 解释

给出一种最优方案:选择链 262 \to 66106 \to 10111511 \to 15161916 \to 19

样例 #2 解释

由于每一条长度为 44 的链权值均为负数,所以不选最优。

数据范围

对于 100%100\% 的数据,2n2×1052 \leq n \leq 2 \times 10^5109ai109-10^9 \leq a_i \leq 10^9