← 返回题目列表

AtCoder · waipc_qual_c

C. 奇偶计数器

中文机器翻译题面 查看原题

配点 : 800 点

問題文

1 减去 N 编号最多为 N 有一棵由顶点组成的无向树。 边上有编号到 1 减去 N-1 ,并且每条边都有 i 是顶点 是 A_i 与 边缘 B_i 已连接。 请回答以下有关

各辺 i 有 直到 2 个计数器 x_i,y_i 。 最初,进行至少x_i=y_i=0 。 求放置超过

您现在将执行以下操作: 执行 0 次操作。

  • 可以自由选择树上的行走路径。 更确切地说,顶点序列 (v_0,v_1,\ldots,v_k) (頂点 v_i,v_{i+1} 是直接由边连接的,可以选择任意长度 k 的行走。 连接顶点 v_i,v_{i+1} 的边称为边 e_i 。 然后,每个 i=0,2,4,\ldots ,x_{e_i} 的值通过 1 增加。 同样,每个 i=1,3,5,\ldots ,y_{e_i} 的值通过 1 增加。 此外,如果同一条边出现多次,则每次出现时计数器的数值都会增加。

每条边都有一个应达到的目标计数器值 X_i,Y_i 。 你的目标是,使所有边的计数器值都 (x_i,y_i)=(X_i,Y_i) 是使其处于这样的状态。请判断目标是否可以实现。若可能,请求出为此所需的最少操作次数。

1 个输入中,T 请解决案例。

制約

  • 1 \leq T \leq 125000
  • 2 \leq N \leq 250000
  • 1 \leq A_i,B_i \leq N
  • 0 \leq X_i,Y_i \leq 10^9
  • 输入图是一棵树
  • T 涉及案例。 N 的总和是 250000 以下
  • 所有输入均为整数

入力

输入是按以下格式从标准输入给出的。

T
case_1
case_2
\vdots
case_T

每个测试案例以下列形式给出。

N
A_1 B_1 X_1 Y_1
A_2 B_2 X_2 Y_2
\vdots
A_{N-1} B_{N-1} X_{N-1} Y_{N-1}

出力

对于每个测试用例,如果无法实现目标, -1 否则请输出实现目标所需的最少操作次数。


入力例 1

4
3
1 2 2 0
2 3 0 1
3
1 2 1 0
2 3 0 2
5
2 3 3 3
3 5 5 2
1 4 2 4
4 5 1 1
10
3 10 0 16306834
6 8 123600023 90587973
10 1 35502434 4326053
1 9 0 6983702
10 2 0 11702429
6 5 0 53901118
10 4 82799399 29529115
10 8 72275777 16348135
6 7 0 21602025

出力例 1

2
-1
-1
215877450

例如, 当分解为1 关于第 番测试用例,可以通过进行以下 2 次操作来实现目标。

  • 步行 (1,2,3) , 所有满足x_1,y_2 的值通过 1 增加。
  • 步行 (2,1) , 所有满足x_1 的值通过 1 增加。

2 th 和 由于您拿了第 3 对于第 番测试用例,无论如何都无法实现目标。