# D. Weighting a Tree

time limit per test：2 seconds
memory limit per test：256 megabytes
input：standard input
output：standard output

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 c1, c2, …, cn, each of them is between  - n and n, inclusive. It is also guaranteed that the parity of cv 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·n2 and n2 (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 cv, or determine that this is impossible.

### Input

The first line contains two integers n and m (2 ≤ n ≤ 105n - 1 ≤ m ≤ 105) — the number of vertices and the number of edges.

The next line contains n integers c1, c2, …, cn ( - n ≤ ci ≤ n), where ci is the required sum of weights of edges connected to vertex i. It is guaranteed that the parity of ci 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 ai and bi (1 ≤ ai, bi ≤ nai ≠ bi), meaning that the i-th edge connects vertices ai and bi.

It is guaranteed that the given graph is connected and does not contain loops and multiple edges.

### Output

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 wi ( - 2·n2 ≤ wi ≤ 2·n2).

# E. Cyclic Cipher

time limit per test：5 seconds
memory limit per test：256 megabytes
input：standard input
output：standard output
Senor Vorpal Kickass’o invented an innovative method to encrypt integer sequences of length n. To encrypt a sequence, one has to choose a secret sequence , that acts as a key.

Vorpal is very selective, so the key should be such a sequence bi, that its cyclic shifts are linearly independent, that is, there is no non-zero set of coefficients x0, x1, …, xn - 1, such that  for all k at the same time.

After that for a sequence  you should build the following cipher:

In other words, you are to compute the quadratic deviation between each cyclic shift of bi and the sequence ai. The resulting sequence is the Kickass’s cipher. The cipher is in development right now and Vorpal wants to decipher a sequence after it has been encrypted. You are to solve this problem for him. You are given sequences ci and bi. You are to find all suitable sequences ai.

### Input

The first line contains a single integer n ().

The second line contains n integers b0, b1, …, bn - 1 ().

The third line contains n integers c0, c1, …, cn - 1 ().

It is guaranteed that all cyclic shifts of sequence bi are linearly independent.

### Output

In the first line print a single integer k — the number of sequences ai, such that after encrypting them with key bi you get the sequence ci.

After that in each of k next lines print n integers a0, a1, …, an - 1. Print the sequences in lexicographical order.

Note that k could be equal to 0.

# 以下为官方题解（前五题为Div. 2，后五题为Div. 1）

### 902A – Visiting a Friend

Note that if we can get to some point x, then we can get to all points <= x. So we can support the rightmost point where we can get to. Then if this point can use the teleport (if this point is to the right of the teleport), we’ll try to move it (If the limit of the teleport is to the right of the current point, then move it there). Then in the end we need to check that the rightmost point where we can get is equal to M.

### 902B – Coloring a Tree

Consider the process from the end, we will “delete” any subtree from the tree, whose color of the ancestor of the highest vertex differs from the color of the highest vertex and the colors of all vertices in the subtree are the same. Thus, we can show that the answer is the number of edges whose ends have different colors + 1.

### 901A – Хешируем деревья

There are many ways to solve the problem. First of all you should build any single tree. To do this, you first build the longest path from the root and then attach remained vertices on proper heights. Thus each vertex is either on the longest path or has parent on this path. To build the second tree you should use different vertices from previous levels during construction to make it different from first tree. This is always possible if there are two consecutive ai > 1. Otherwise the tree is determined uniquely by ai sequence.

### 901B – НОД многочленов

As for integers it is well known that worst case are consequent Fibonacci’s numbers Fn + 1 = Fn + Fn - 1. Solutions to this problem are based on the same idea. There were two main intended solutions. First of all you should note that sequence

p0 = 1, p1 = x,
pn + 1 = x·pn ± pn - 1
Gives us the family of solutions, we just have to output pn and pn - 1. It can be directly checked for given constraints that you can always choose  +  or  -  to satisfy coefficients constraints.

The other solution is the same sequence but you use  +  instead of  ±  and take coefficients modulo 2. That’s true because if remainders sequence has k steps while you consider numbers by some modulo it will have at least k steps in rational numbers. So the second intended solution is

p0 = 1, p1 = x,

### 901C – Bipartite Segments

If two cycles of odd length intersect, then they can be bypassed so as to obtain an edge-simple cycle of even length.

It follows that the given graph is a vertex cactus, with cycles of odd length, then the vertex segment is good – if there is no loop, that the vertex with the minimum number from this cycle is present on this segment and the vertex with the maximum number from this cycle is present on this segment. Then we can select all the cycles, and now we work with the segments.

Let us find for each vertex a maximal right boundary such that the interval [i..mxi] is a bipartite graph.

Then mxi is equal to the minimal right boundary of the segment, which was opened later i.

This can be considered a minimum on the suffix, initially setting for all cycles mx[minimum on the cycle] = maximum on the cycle

To answer the query, we need to take the sum over mxi - i + 1 for those who have mxi ≥ r and the sum over r - i + 1 for those who have mxi ≥ r

then we note that mxi increases and we simply need to find the first moment when mxi becomes  ≥ r (we can do it with binary search)

And take two prefix sums – sum of (mxi - i + 1) and sum of i.

### 901D – Weighting a Tree

Let’s solve two cases.

First case is when graph is the bipartite graph

Then the sum of weights of the left part should be equal to the sum of weights of the right part (because each edge will bring an equal contribution to the sums of both part).

We will leave any spanning tree of this graph, then for it the solution is unique (take the edges entering the leafs, their weights are uniquely determined, subtract weights from weights of the second ends of this edges, delete the leafs, recursively) this solution can be found with dfs, then in the end, the root will has weight 0 (because sum of weights of the left part equal to the sum of weights of the right part) Thus, the answer exists when the sum of the weights of the left part is equal to the sum of the weights of the right part.

Second case when graph has the odd cycle.

We find an odd cycle, root the tree for any of its vertices, solve the tree. Then, we add to the weights of the edges of the cycle adjacent to the root minus its weight divided by 2 (it is even, because it is the sum of the weights of all vertices (with different signs) equal to the sum of the degrees of vertices by modulo 2). , and for all others we alternate the signs with which we add this value, then for all vertices except the root the sum does not change, but for the root we get the required value.

Example code: https://pastebin.com/b2bGp4Bh

### 901E – Cyclic Cipher

(a - b)2 = a2 + b2 - 2ab, hence, . Let ai = ai - ai - 1. Then . This corresponds to cyclic convolution of polynomials  and . These polynomials uniquely determined by values in roots of unity of degree n. Thus we can divide values of C by values of B in this points and return to polynomials from values in roots of unity. To do this one should compute discrete Fourier Transform in arbitrary length polynomial which can be done by Bluestein’s algorithm. Note that you can’t use complex fft here because real values can be very close to zero leading to great precision issues. Thus you should find some mod having root of unity of degree 2nand compute discrete transform over it. Thus we will find dk = ak - a0 for each k, which will allow us to recover a0, because .

It can be proven that values of polynomial in roots of unity are eigenvalues of matrix of linear system thus cyclic shifts are linearly independent iff there is such mod which has root of unity of degree n and values of polynomial in all such roots doesn’t equal zero. If it’s true for polynomial in field of real numbers there will be only finite number of mods in which this may not be true (it only true if  of polynomial and xn - 1 isn’t equal 1 in such mod).