分数: 600 点
问题陈述
Kenkoooo 发现了一个简单的连通图。 顶点已编号 1 通过 n。 的 i第一条边连接顶点 u_i 和 v_i,并且有一个固定整数 s_i.
Kenkoooo 正在尝试写一个 正整数 在每个顶点中,以满足以下条件:
- 对于每条边 i,Vertex 中写入的正整数之和 u_i 和 v_i 等于 s_i.
找出在顶点中写入正整数的这种方式的数量。
约束
- 2 \leq n \leq 10^5
- 1 \leq m \leq 10^5
- 1 \leq u_i < v_i \leq n
- 2 \leq s_i \leq 10^9
- If i\neq j,那么 u_i \neq u_j or v_i \neq v_j.
- 该图已连接。
- 输入中的所有值都是整数。
输入
输入由标准输入按以下格式给出:
n m u_1 v_1 s_1 : u_m v_m s_m
输出
打印在顶点中写入正整数以满足条件的方式数。
示例输入 1
3 3 1 2 3 2 3 5 1 3 4
示例输出 1
1
如果我们写,则满足条件 1,2 和 3 在顶点 分别为 1,2 和 3。 没有其他方法可以满足条件,所以答案是 1.
示例输入 2
4 3 1 2 6 2 3 7 3 4 5
示例输出 2
3
让 a,b,c 和 d 是要写入顶点的数字 分别是 1,2,3 和 4。 有三个四元组 有 (a,b,c,d) 满足条件:
- (a,b,c,d)=(1,5,2,3)
- (a,b,c,d)=(2,4,3,2)
- (a,b,c,d)=(3,3,4,1)
示例输入 3
8 7 1 2 1000000000 2 3 2 3 4 1000000000 4 5 2 5 6 1000000000 6 7 2 7 8 1000000000
示例输出 3
0