Tree Painting#11002

Tree Painting (Editorial)

The total number of points obtained is uniquely determined by the first chosen vertex. Therefore, it is sufficient to consider all possible starting vertices, compute the total number of points for each of them, and take the maximum.

Let us run a depth-first search starting from vertex $1$ and compute the value $w e i g h t [v]$ weight[v] — the size of the subtree rooted at vertex $v$ (i.e., the number of vertices in the subtree of $v$ ). Let $t o_{1}, t o_{2}, ..., t o_{k}$ to_1, to_2, ..., to_k be the children of $v$ . Then the following formula holds:

w e i g h t [v] = 1 + w e i g h t [t o_{1}] + w e i g h t [t o_{2}] + ... + w e i g h t [t o_{k}]

weight[v] = 1 + weight[to_1] + weight[to_2] + ... + weight[to_k]

The second depth-first search visits all vertices and allows us to recompute the maximum number of points that can be obtained if the game starts from a given vertex.

Consider the function dfs2. Suppose we are at vertex $v$ , and its parent is vertex $p$ . If we choose vertex $v$ as the first move, then the number of points obtained is $s$ .

v o i d df s 2 (in t v, in tp, l o n g l o n g s)

void~dfs2(int~v,~int p,~long~long~s)

Make a transition along the edge $(v, t o)$ (v, to) and show how to compute the answer if the game starts from vertex $t o$ . In fact, we are performing a rerooting of the tree: the root is moved from vertex $v$ to vertex $t o$ .

On the left, a tree rooted at $v$ is shown. The vertex $t o$ is one of its descendants, while $p$ is its parent. On the right, the tree is shown rooted at $t o$ .

To compute $w e i g h t [t o]$ weight[to] in the right tree, we need to subtract $w e i g h t [t o]$ weight[to] of the left tree from the value $s$ and add the number of vertices in the region marked with a dashed line. This number is equal to $n - w e i g h t [t o]$ n - weight[to].

Example

Let the first chosen vertex be $1$ . Then the total number of points obtained is $25$ .

If the first chosen vertex is $2$ , then the number of points obtained is $26$ . We move from vertex $1$ to vertex $2$ as follows: subtract $w e i g h t [2] = 4$ weight[2] = 4 from $s = 25$ s = 25 and add $(9 - w e i g h t [4]) = 5$ (9 - weight[4]) = 5. As a result, we get $25 - 4 + 5 = 26$ 25 - 4 + 5 = 26, which is the value of $s$ for the tree rooted at vertex $2$ .

The maximum number of points is $36$ , and it is achieved if the game starts from vertex $7$ .

Exercise

Consider the following tree:

Suppose vertex $1$ is chosen as the first move. Find the number of points obtained.
Move the root from vertex $1$ to vertex $3$ and compute the number of points obtained.
Then move the root from $3$ to $4$ , from $3$ to $5$ , and from $3$ to $6$ . Solve each of the resulting cases.

Algorithm implementation

Define the adjacency list of the graph $g$ .

vector<vector<int>> g;
vector<int> weight;

The function dfs1 performs a depth-first search starting from a vertex $v$ whose parent is vertex $p$ . During this process, $w e i g h t [v]$ weight[v] is computed — the size of the subtree rooted at vertex $v$ , i.e., the number of vertices in this subtree.

void dfs1(int v, int p)
{
  weight[v] = 1;
  for (int to : g[v])
    if (to != p)
    {
      dfs1(to, v);
      weight[v] += weight[to];
    }
}

C++

The function dfs2 performs a depth-first search starting from a vertex $v$ whose parent is vertex $p$ . If the first move of the game is to choose vertex $v$ , then the number of points obtained is $s$ .

void dfs2(int v, int p, long long s)
{
  res = max(res, s);
  for (int to : g[v])
    if (to != p) dfs2(to, v, s - weight[to] + n - weight[to]);
}

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

scanf("%d", &n);
g.resize(n + 1);
weight.resize(n + 1);
for (i = 1; i < n; i++)
{
  scanf("%d %d", &a, &b);
  g[a].push_back(b);
  g[b].push_back(a);
}

C++

Start a depth-first search from vertex $1$ .

dfs1(1, 0);

Compute the sum of all elements in the array $w e i g h t$ weight using the variable $s$ . This value is equal to the total number of points obtained if we choose vertex $1$ as the first move in the game.

s = 0;
for (i = 1; i <= n; i++)
  s += weight[i];

Start the second depth-first search from vertex $1$ .

dfs2(1, 0, s);

Print the answer.

printf("%lld\n", res);