#P17917. Connecting Railway Stations
Connecting Railway Stations
有一棵包含 个顶点的无向树,顶点编号为 。树中所有度数为 的顶点都设有车站,保证车站数为偶数。
你要把所有车站两两配对,每个车站恰好属于一对。每一对车站之间开通一条列车线路,线路沿树上连接这两个顶点的唯一简单路径运行。线路长度为这条路径包含的边数。
第 条边的容量为 ,经过这条边的列车线路数不能超过 。不同线路可以共用边,只要不超过容量。
求所有线路长度之和的最大值。如果不存在满足要求的配对,输出 。
输入格式
第一行一个整数 。
接下来 行,每行三个整数 ,表示一条连接 与 、容量为 的无向边。
输出格式
输出一个整数,表示最大线路总长度;无解时输出 。
数据范围
- 。
- ,。
- 输入的边构成一棵树。
- 度数为 的顶点数为偶数。
- 每个输入文件只有一组数据。
样例 1
10
1 2 2
2 3 1
3 4 3
5 1 1
6 1 2
7 2 3
8 3 2
9 3 1
10 4 7
10
配对 、、,三条线路长度分别为 ,总长度为 。
样例 2
5
1 2 3
1 3 1
1 4 0
1 5 2
-1