Tree Operation

If $N=1$, performing the operation on the only vertex makes its value $1$. Therefore, the answer is $1$.

Now assume $N \ge 2$.

First, no vertex can have final value at least $3$. For a vertex $v$ to become at least $3$, every neighbor of $v$ must have value at least $2$ right before the operation on $v$. However, if a neighbor $$ of was operated before and became at least , then at that time its neighbor should already have value at least . But had not been operated yet, so its value was still . This is a contradiction. Thus, final values can only be .

For $N \ge 2$, we can make every vertex at least $1$. For example, perform the operation on every vertex in any order. Since the minimum adjacent value is always at least $0$, each operated vertex becomes at least $1$.

Now consider the vertices whose final value is $2$. No two adjacent vertices can both have value $2$. Suppose adjacent vertices $u$ and $v$ both become $2$. Let $u$ be the one operated earlier. When $u$ was operated, had not been operated yet, so its value was . Therefore, could not become , a contradiction.

So the set of vertices with value $2$ must be an independent set.

Conversely, for any independent set $S$ in the tree, we can make exactly those vertices have value $2$. First, perform the operation on all vertices not in $S$. Their values become at least $1$. Then perform the operation on all vertices in $S$. Since $S$ is independent, every neighbor of each vertex in lies outside and already has value at least . Thus, every vertex in becomes .

Therefore, for $N \ge 2$, the maximum sum is

$$N + \alpha,$$

where $\alpha$ is the size of a maximum independent set of the tree.

The maximum independent set of a tree can be computed by dynamic programming. Root the tree at vertex $1$ and define:

• $dp0[v]$: the maximum number of chosen vertices in the subtree of $v$ when $v$ is not chosen
• $dp1[v]$: the maximum number of chosen vertices in the subtree of $v$ when is chosen

Then:

$$dp1[v] = 1 + \sum_{u \text{ child of } v} dp0[u],$$ $$dp0[v] = \sum_{u \text{ child of } v} \max(dp0[u], dp1[u]).$$

The maximum independent set size is $\max(dp0[1], dp1[1])$, and the answer is $N+\max(dp0[1],dp1[1])$.

The time complexity is $O(N)$, and the memory usage is $O(N)$.