← 返回题目列表

AtCoder · soundhound2018_summer_qual_e

E. + 图

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

分数: 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