#P17917. Connecting Railway Stations

Connecting Railway Stations

有一棵包含 NN 个顶点的无向树,顶点编号为 1,2,…,N1,2,\ldots,N。树中所有度数为 11 的顶点都设有车站,保证车站数为偶数。

你要把所有车站两两配对,每个车站恰好属于一对。每一对车站之间开通一条列车线路,线路沿树上连接这两个顶点的唯一简单路径运行。线路长度为这条路径包含的边数。

第 ii 条边的容量为 cic_i,经过这条边的列车线路数不能超过 cic_i。不同线路可以共用边,只要不超过容量。

求所有线路长度之和的最大值。如果不存在满足要求的配对,输出 −1-1。

输入格式

第一行一个整数 NN。

接下来 N−1N-1 行,每行三个整数 ai,bi,cia_i,b_i,c_i,表示一条连接 aia_i 与 bib_i、容量为 cic_i 的无向边。

输出格式

输出一个整数,表示最大线路总长度;无解时输出 −1-1。

数据范围

  • 2≤N≤2000002\le N\le 200000。
  • 1≤ai,bi≤N1\le a_i,b_i\le N,0≤ci≤N0\le c_i\le N。
  • 输入的边构成一棵树。
  • 度数为 11 的顶点数为偶数。
  • 每个输入文件只有一组数据。

样例 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

配对 (5,9)(5,9)、(6,7)(6,7)、(8,10)(8,10),三条线路长度分别为 4,3,34,3,3,总长度为 1010。

样例 2

5
1 2 3
1 3 1
1 4 0
1 5 2
-1