Contest Duration: - (local time) (100 minutes) Back to Home
Official

## B - Values Editorial by evima

In one operation, the sum of values on the two vertices connected by the chosen edge does not change. Furthermore, the sum of values in the connected component containing the chosen edge does not change.

Thus, to make the value on each vertex $$b_i$$, the following must hold for each connected component $$C$$:

$\displaystyle \sum_{v \in C} a_v= \sum_{v \in C} b_v$

It turns out that, if the above holds, we can always make the value on each vertex $$b_i$$ with proper operations. We will prove it from now on.

First, by mathematical induction, we will show the following: for every integer $$N$$ at least $$1$$, (★) if a tree with $$N$$ vertices and sequences $$a,b$$ are given and 1. is satisfied, it is possible to make the value on each vertex $$b_i$$ with proper operations.

If $$N=1$$, $$a_1=b_1$$ follows from 1., so the objective is acheived with zero operations.

Assume that (★) holds for $$N=K$$. We now have to show that (★) holds for $$N=K+1$$. Let us assume that a tree with $$N+1$$ vertices and sequences $$a,b$$ of length $$N+1$$ are given and 1. is satisfied.

We randomly choose a leaf in the tree. Let $$l$$ be the leaf, and $$m$$ be the vertex connected to the leaf with an edge. Let us choose the edge connecting $$l$$ and $$m$$ multiple times in operations to increase $$a_l$$ by $$+b_l-a_l$$ and $$a_m$$ by $$+a_l-b_l$$. After these operations, the sums of $$a$$ and $$b$$ over the vertices except $$l$$ will be equal.

(We can see this from the following facts. First, the premise in (★) guarantees that the sums of $$a$$ and $$b$$ are equal. Second, $$a_l = b_l$$ holds after the operations.)

Consider the subgraph obtained by removing $$l$$ from the tree after the operations. $$l$$ was a leaf, so this subgraph will be a tree again. Additionally, this tree has $$K$$ vertices, and the sums of $$a$$ and $$b$$ are equal. Thus, from the induction assumption, we can change the value on each vertex $$v$$ except $$l$$ to $$b_v$$. Since we already made the value on $$l$$ $$b_l$$, we have shown that (★) also holds for $$N=K+1$$.

We know from the above argument that 1. is the sufficient condition for a graph that is a tree. If the given graph is not a tree, we can decompose the graph into connected components and pick up the spanning tree within each connected component to reduce the problem to the tree version.

posted:
last update: