#P8827. [2023联测]旅行计划
[2023联测]旅行计划
旅行计划
题目描述
YeahPotato 到自然公园去旅行!
自然公园的景点可以抽象成 个节点,景点之间由固定的班车连接,班车可以双向地运送旅客,也就是说班车可以抽象成边。一共有 对景点之间有班车,任意两个景点之间都可以互相到达。不过这 对景点中有一部分对的两点间可能有 部班车(且它们的实地路线除端点外略有不同),也就是说,自然公园可以抽象成一棵有重边的树。
YeahPotato 考虑坐直升机先到达一个景点(起点),然后走过一些边到达另一个景点(终点,可以与起点重合)后再坐直升机离开。本着“风景在路上”的理念,YeahPotato 希望看到尽量多的风景,也就是走尽量多的边。他不希望重复经过一条边 (同一条边的两个方向只能走一个),不过可以重复经过点。
给定自然公园的地图,求 YeahPotato 最多能经过几条边。
输入格式
本题有多组数据。第一行一个整数。
每组数据第一行一个整数 。
接下来 行,第 行三个整数,分别表示一对有边的景点以及它们之间班车(重边)数。 保证输入构成一棵树。
输出格式
输出 行,每行一个整数依次表示每组输入的答案。
样例输入1
3
4
3 1 1
2 4 1
2 3 2
5
1 2 1
1 3 1
1 4 1
1 5 2
5
2 3 1
3 1 2
3 4 3
4 5 4
样例输出1
3
4
10
样例解释 1

补充样例 2
1
1
0
只有一个景点,没有班车可经过。
补充样例 3
1
4
1 2 1
1 3 1
1 4 1
2
不能重走边,最多经过两个叶子之间的两条边。
补充样例 4
1
3
1 2 2
2 3 2
4
可以依次走 ,每次使用不同的班车。
数据范围
记 为单组数据内的边数总和, 为一个测试点内所有组的 之和。
- 测试点1:。
- 测试点2:。
- 测试点3、4、5:,即原树为链。
- 测试点3、7、8:。
- 测试点4、7、9:。
- 测试点6:。
- 测试点9:。
- 测试点10:无额外限制。
提示
输入量较大,请使用较快的输入方式。
标程配套头文件:exact_integer.h。