# Editorial

For each vertex $v$, compute the number of vertices $sum[v]$ in the subtree where it is the root. If $to_{1},to_{2},...,to_{k}$ are the children of vertex $v$, then

If vertex $v$ is a leaf of the tree, then $sum[v]=1$.

Let $dp[v]$ be the number of saved vertices in the subtree with root $v$, assuming that currently vertex $v$ (and only it in the subtree) is infected.

If vertex $v$ has only one child $to$, then $dp[v]=sum[to]−1$ (the removed vertex $to$ is not considered saved).

Let vertex $v$ have two children $to_{1}$ and $to_{2}$ (each vertex has a degree of at most $3$). Then we have two options:

Remove $to_{1}$ and recursively save the vertices in the subtree with root $to_{2}$. The number of saved vertices will be sum $sum[to_{1}]−1+dp[to_{2}]$.

Remove $to_{2}$ and recursively save the vertices in the subtree with root $to_{1}$. The number of saved vertices will be $sum[to_{2}]−1+dp[to_{1}]$.

Among the two options, choose the one that maximizes the number of saved vertices.

Consider the depth-first search process when examining the edge $(v,to)$.

Let $a$ be the second child of vertex $v$ that we have not yet visited. We need to compute the value $dp[to]+sum[a]−1$. Since vertex $a$ is not visited yet, the value $sum[a]$ is not computed. However, we know that:

From which it follows that:

Thus,

Iterate over the children $to$ of the vertex $v$ and compute:

Example

In the first example, Huseyn is able to save two vertices, $3$ and $4$, by choosing vertex number $2$ as his first move.|

Consider the second example. Next to each vertex $v$, place the labels $sum[v]/dp[v]$. The vertices chosen by Huseyn are displayed in green.

For example,

Algorithm implementation

Declare the arrays.

#define MAX 300005 int sum[MAX], dp[MAX]; vector<vector<int>> g;

The function dfs performs a depth-first search starting from vertex $v$. The parent of vertex $v$ is $p$.

void dfs(int v, int p = -1) {

Initialize the variables $sum[v]$ and $dp[v]$.

sum[v] = 1; dp[v] = 0;

Perform a depth-first search starting from the children of vertex $v$.

for (int to : g[v]) if (to != p) { dfs(to, v); sum[v] += sum[to]; }

Compute the value of $dp[v]$.

for (int to : g[v]) if (to != p) { dp[v] = max(dp[v], sum[to] - 1); // if 1 son dp[v] = max(dp[v], dp[to] + sum[v] - sum[to] - 2); } }

The main part of the program. Read the input data.

scanf("%d", &n); g.clear(); g.resize(n + 1); memset(dp, 0, sizeof(dp)); memset(sum, 0, sizeof(sum)); for (i = 1; i < n; i++) { scanf("%d %d", &u, &v); g[u].push_back(v); g[v].push_back(u); }

Perform a depth-first search starting from vertex $1$.

dfs(1);

Print the answer.

printf("%d\n", dp[1]);