#P1859. 2024.7.27-OPPO-第三题-小 O 的树上路径(第三套)

2024.7.27-OPPO-第三题-小 O 的树上路径(第三套)

题意

小 O 有一棵树,树上的每一条边都有一个权值 ww, 他现在想要选择其中一个一定价值的物品, 从 11 号点开始,每个点最多只能经过一次,小 O 想知道最多可以拿到多少价值的物品。

输入

第一行输入一个整数 n(2≤n≤105)n (2 \leq n \leq 10^5), 表示树上的点数。

此后 n−1n-1 行, 每行输入三个整数 u,vu, v 和 w(1≤u,v≤n;1≤w≤109)w (1 \leq u, v \leq n; 1 \leq w \leq 10^9) 表示 uu 和 vv 之间有一条权值为 ww 的边。

输出

在一行上输出一个整数,表示小 O 最多能拿到的物品价值。

样例1

输入

3
1 2 1
2 3 2

输出

3

样例2

输入

6
1 2 1
2 3 2
1 4 3
4 5 1
4 6 1

输出

8

样例3

输入

8
1 2 1
2 3 2
1 4 3
4 5 1
4 6 1
3 7 10
3 8 10

输出

27

知识点:*****

查看知识点以及同类型题目

Statistics