Weighting a Tree

题意翻译

## 题目描述 给你一个有 $n$ 个顶点与 $m$ 条边的无向图，那些顶点的编号依次为 $1$ 到 $n$。 再给你 $n$ 个整数 $C[1],c[2],…,C[n]$，每一个数都在区间 $[-n,n]$ 之间。保证 $C[v]$ 的奇偶性与顶点 $v$ 的度的奇偶性相同。一个顶点的的度是指连接到它的边数。 你需要按照下列的要求为所有边写上一个在 $-2\cdot n^2$ 与 $2\cdot n^2$ 之间的一个重量：对于任何一个顶点 $v$，所有连接到这个顶点的边的重量和等于 $C[v]$。或者，确定这是不可能达到的。 ## 输入输出格式 ###### 输入格式： 第一行是两个整数 $n$ 和 $m$ $\ (2\le n\le 10^5$,$n-1\le m\le 10^5)$，为边与顶点的个数。 第二行有 $n$ 个整数 $C[1],C[2]……C[n]\ (-n\le C[i]\le n$)，$C[i]$ 是连接到 $i$ 的边的权值之和。保证 $C[v]$ 的奇偶性与顶点 $v$ 的度的奇偶性相同。 之后的 $m$ 行是用来描述无向图的边的。对于第 $i$ 行，有 $a[i]$ 和 $b[i]$ 两个整数$\ (1\le a[i],b[i]\le n,a[i]≠b[i])$，表示第 $i$ 条边连接点 $a[i]$ 和 $b[i]$ 。 保证给出的无向图是联通的且不含有重边与自环。 ###### 输出格式： 如果无解，输出"NO"。 否则输出"YES"和$m$行，每一行表示对应编号的边的权值。 Translated by @Microelectronics

题目描述

You are given a connected undirected graph with $ n $ vertices and $ m $ edges. The vertices are enumerated from $ 1 $ to $ n $ . You are given $ n $ integers $ c_{1},c_{2},...,c_{n} $ , each of them is between $ -n $ and $ n $ , inclusive. It is also guaranteed that the parity of $ c_{v} $ equals the parity of degree of vertex $ v $ . The degree of a vertex is the number of edges connected to it. You are to write a weight between $ -2·n^{2} $ and $ 2·n^{2} $ (inclusive) on each edge in such a way, that for each vertex $ v $ the sum of weights on edges connected to this vertex is equal to $ c_{v} $ , or determine that this is impossible.

输入输出格式

输入格式

The first line contains two integers $ n $ and $ m $ ( $ 2<=n<=10^{5} $ , $ n-1<=m<=10^{5} $ ) — the number of vertices and the number of edges. The next line contains $ n $ integers $ c_{1},c_{2},...,c_{n} $ ( $ -n<=c_{i}<=n $ ), where $ c_{i} $ is the required sum of weights of edges connected to vertex $ i $ . It is guaranteed that the parity of $ c_{i} $ equals the parity of degree of vertex $ i $ . The next $ m $ lines describe edges of the graph. The $ i $ -th of these lines contains two integers $ a_{i} $ and $ b_{i} $ ( $ 1<=a_{i},b_{i}<=n $ ; $ a_{i}≠b_{i} $ ), meaning that the $ i $ -th edge connects vertices $ a_{i} $ and $ b_{i} $ . It is guaranteed that the given graph is connected and does not contain loops and multiple edges.

输出格式

If there is no solution, print "NO". Otherwise print "YES" and then $ m $ lines, the $ i $ -th of them is the weight of the $ i $ -th edge $ w_{i} $ ( $ -2·n^{2}<=w_{i}<=2·n^{2} $ ).

输入输出样例

输入样例 #1

3 3
2 2 2
1 2
2 3
1 3

输出样例 #1

YES
1
1
1

输入样例 #2

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

输出样例 #2

YES
-1
1
1

输入样例 #3

6 6
3 5 5 5 1 5
1 4
3 2
4 3
4 5
3 5
5 6

输出样例 #3

YES
3
5
3
-1
-3
5

输入样例 #4

4 4
4 4 2 4
1 2
2 3
3 4
4 1

输出样例 #4

NO