#P8827. [2023联测]旅行计划

    ID: 8921 传统题 4000ms 512MiB 尝试: 3 已通过: 2 难度: 7 上传者: 标签>图论贪心动态规划CF2200树形DP数学直径最短路

[2023联测]旅行计划

旅行计划

题目描述

YeahPotato 到自然公园去旅行!

自然公园的景点可以抽象成nn 个节点,景点之间由固定的班车连接,班车可以双向地运送旅客,也就是说班车可以抽象成边。一共有n−1n-1 对景点之间有班车,任意两个景点之间都可以互相到达。不过这 n−1n-1 对景点中有一部分对的两点间可能有 >1> 1 部班车(且它们的实地路线除端点外略有不同),也就是说,自然公园可以抽象成一棵有重边的树。

YeahPotato 考虑坐直升机先到达一个景点(起点),然后走过一些边到达另一个景点(终点,可以与起点重合)后再坐直升机离开。本着“风景在路上”的理念,YeahPotato 希望看到尽量多的风景,也就是走尽量多的边。他不希望重复经过一条边 (同一条边的两个方向只能走一个),不过可以重复经过点。

给定自然公园的地图,求 YeahPotato 最多能经过几条边。

输入格式

本题有多组数据。第一行一个整数TT。

每组数据第一行一个整数 nn。

接下来n−1n-1 行,第i+1i+1 行三个整数ui,vi,wiu_{i} , v_{i} , w_{i},分别表示一对有边的景点以及它们之间班车(重边)数。 保证输入构成一棵树。

输出格式

输出TT 行,每行一个整数依次表示每组输入的答案。

样例输入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→2→11\to2\to3\to2\to1,每次使用不同的班车。

数据范围

记 ∑w\sum w 为单组数据内的边数总和,∑n\sum n 为一个测试点内所有组的 nn 之和。

  • 测试点1:n,∑w≤7, T≤100n,\sum w\le7,\ T\le100。
  • 测试点2:n,∑w≤18, T≤100n,\sum w\le18,\ T\le100。
  • 测试点3、4、5:ui=i,vi=i+1u_i=i,v_i=i+1,即原树为链。
  • 测试点3、7、8:n≤3000,∑n≤15000n\le3000,\sum n\le15000。
  • 测试点4、7、9:wi≥2w_i\ge2。
  • 测试点6:n≤300,∑n≤1500n\le300,\sum n\le1500。
  • 测试点9:n≤105,∑n≤3×105n\le10^5,\sum n\le3\times10^5。
  • 测试点10:无额外限制。

提示

输入量较大,请使用较快的输入方式。

标程配套头文件:exact_integer.h。