Auto comment: topic has been updated by pure_mem (previous revision, new revision, compare).

Auto comment: topic has been updated by pure_mem (previous revision, new revision, compare).

Note that the operation doesn't change the parity of sum of values on a connected component. Iterate over each connected component $$$C$$$. Let $$$size(C)$$$ be the number of vertices in $$$C$$$ and $$$sum(C)$$$ the sum of values of all vertices in $$$C$$$. We now do bunch of caseworks.

(1) $$$C$$$ is non-bipartite.

• Note that using any odd cycle, we can do $$$value[u]+=1, value[v]-=1$$$ on arbitrary pair of vertices in $$$C$$$.

(1-1) $$$size(C)$$$ is even.

• After all the values become equal, $$$sum(C)$$$ is even, so it had to be even initially. Print "NO" if $$$sum(C)$$$ is odd. Otherwise, you can make all vertices of $$$C$$$ equal to an arbitrary integer.

(1-2) $$$size(C)$$$ is odd.

• After all the values become equal to $$$x$$$, $$$sum(C)=size(C)*x$$$, so the parity of $$$x$$$ must match the initial parity of $$$sum(C)$$$. Conversely, you can make all the values of $$$C$$$ equal to arbitrary such $$$x$$$. So this forces the answer to have the same parity as $$$sum(C)$$$.

(2) $$$C$$$ is bipartite.

• Iterate over the bipartitions $$$P$$$ of $$$C$$$, and let $$$Q$$$ be the other partition.

(2-1) $$$size(C)=1$$$

• We can't do any operations on $$$C$$$ so we force the answer to be equal to the value of the vertex of $$$C$$$.

(2-2) $$$size(C)\ge 2$$$

• Note that a single operations correspond to operating on a two distinct vertices on a bipartition with a shared neighbor. We think of a new graph $$$G$$$ over the bipartitions of $$$C$$$ where two vertices are connected if and only if they have a common neighbor in the original graph. Note that we can't construct this graph explicitly as it can have up to $$$O(size(C)^2)$$$ edges.
• $$$G$$$ currently has exactly $$$2$$$ connected components $$$G(P)$$$ and $$$G(Q)$$$ corresponding to $$$P$$$ and $$$Q$$$ respectively, and a single operation corresponds to picking an adjacent pair of vertices in $$$G$$$ and adding the same integer. We call this a "new operation".

(2-2-1) $$$Q$$$ has a vertex with degree $$$\ge 3$$$ (in the original graph).

• Here, $$$G(P)$$$ has a clique with size $$$\ge 3$$$, implying that it has an odd cycle. Furthermore, the new operation is equivalent to the original operation given the presence of an odd cycle. Therefore, we repeat the exact same argument as (1).

(2-2-2) All the vertices of $$$Q$$$ has degree $$$\le 2$$$ (in the original graph).

• Now we can afford to construct $$$G(P)$$$ explicitly as it has $$$O(size(Q))$$$ edges.

(2-2-2-1) $$$G(P)$$$ is non-bipartite.

• Repeat the argument in (1).

(2-2-2-2) $$$G(P)$$$ is bipartite.

• Let $$$L$$$ and $$$R$$$ be the bipartitions of $$$G(P)$$$. Note that the new operation preserves $$$sum(L) - sum(R)$$$. If all the value of vertices became $$$x$$$, $$$sum(L) - sum(R) = x * (size(L) - size(R))$$$ must hold.

(2-2-2-2-1) $$$size(L) = size(R)$$$.

• If $$$sum(L) \ne sum(R)$$$, print "NO" and exit. Otherwise, you can make all the values equal to arbitrary integer $$$x$$$ by taking any rooted spanning tree of $$$G(P)$$$ and filling out from the leaves.

(2-2-2-2-2) $$$size(L) \ne size(R)$$$.

• If $$$sum(L) - sum(R)$$$ is not a multiple of $$$size(L) - size(R)$$$, print "NO" and exit. Otherwise, the answer is forced to be $$$(sum(L) - sum(R)) / (size(L) - size(R))$$$. This is always possible by repeating the same precedure as the end of (2-2-2-2-1).

Finally, check if all the forcings are consistent. If they are contradictory, print "NO". Otherwise, we've checked for each connected component that all the forced values are possibles, so print "YES".