题目描述

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

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

输入格式

第一行，一个整数 $n$；

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

输出格式

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

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 \to 6$，$6 \to 10$，$11 \to 15$，$16 \to 19$。

样例 #2 解释

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

数据范围

对于 $100\%$ 的数据，$2 \leq n \leq 2 \times 10^5$，$-10^9 \leq a_i \leq 10^9$。