题目描述

题目译自 PA 2021 Runda 2 Poborcy podatkowi

给定一棵 $n$ 个点的树，你可以选择若干条长度恰好为 $4$ 的不交链，可以不选。

方案的收益定义为选出的链的并集的边权和，求最大收益。

输入格式

第一行一个正整数 $n$ ，表示树的节点数。

第二行至第 $n$ 行，每行三个整数 $u$，$v$，$w$，表示 $u$ 和 $v$ 之间有边相连，边权为 $w$。

保证输入的是一棵树。

输出格式

一行一个整数 $ans$， 表示最大收益。

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

数据范围与提示

$2 \leq n \leq 200000$

$-10 ^ 9 \leq a_i \leq 10 ^ 9$