配点 : 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 对于第 番测试用例,无论如何都无法实现目标。