Teto's Emotions#12449

Teto's Emotions (Editorial)

Problem author:	Taras Derkach
Prepared by:	Taras Derkach
Editorial:	Taras Derkach

Solution

Fix a vertex $v$ that we choose as the central vertex.

After that, all vertices at distance exactly $2$ from $v$ are removed.

Let us see which connected components remain.

The first component always contains the vertex $v$ itself and all its neighbors. Denote its sum by $ce n t e r_{v}$ center_v:

ce n t e r_{v} = a_{v} + u \in a d j_{v} \sum a_{u} .

center_v = a_v + \sum_{u \in adj_v} a_u.

Other components can appear only behind the vertices that were removed.

Let $u$ be a neighbor of vertex $v$ , and let $x$ be a neighbor of vertex $u$ , where $x \neq = v$ x \ne v.

Then vertex $x$ is at distance exactly $2$ from $v$ , so it is removed. After removing $x$ , some components may remain behind its other neighbors.

So we need to quickly know the following value:

if there is an edge $(x, y)$ , what is the sum of the component lying on the side of vertex $y$ after removing this edge.

Denote this sum by $s i d e (x, y)$ side(x,y).

If we root the tree at vertex $1$ , then $s i d e (x, y)$ side(x,y) can be easily computed using subtree sums:

if $y$ is a child of $x$ , then $s i d e (x, y) = s u b t r e e_{y}$ side(x,y) = subtree_y;
otherwise, $s i d e (x, y) = t o t a l - s u b t r e e_{x}$ side(x,y) = total - subtree_x.

For each vertex $x$ , we store the two smallest and two largest values among all $s i d e (x, y)$ side(x,y) over all neighbors $y$ .

Why two? Because sometimes we need to take the best value while forbidding one specific direction. For example, when we look at a removed vertex $x$ , we cannot take the direction back to $u$ , because we came to $x$ from there.

Next, for each vertex $u$ , we store the smallest and largest sums of components that may appear after removing one of the neighbors $x$ of vertex $u$ .

In other words, for each neighbor $x$ of vertex $u$ , we take the best component behind $x$ , but not in the direction back to $u$ .

After this preprocessing, the answer for a fixed central vertex $v$ can be found quickly.

First, we have the component with sum $ce n t e r_{v}$ center_v.

Then, for each neighbor $u$ of vertex $v$ , we take the smallest and largest possible component among the vertices located behind $u$ . At the same time, we must forbid the direction back to $v$ .

Among all found components, we find the minimum and maximum sum. The contrast for vertex $v$ is equal to:

ma x S u m - min S u m .

maxSum - minSum.

The answer is the maximum of this value over all vertices $v$ .

Example

In the first example, it is optimal to choose vertex $v = 4$ v = 4.

Then vertex $2$ is at distance exactly $2$ from it, so it is removed.

After the removal, two connected components remain:

${1}$ with sum $1$ ;
${3, 4, 5}$ \{3,4,5\} with sum $3 + 4 + 5 = 12$ 3 + 4 + 5 = 12.

Therefore, the contrast is equal to:

12 - 1 = 11.

12 - 1 = 11.

Complexity

We calculate subtree sums once, and then for each vertex we look through its neighbors.

Each edge is processed only a constant number of times.

Therefore, the complexity of the solution is $O (n)$ .