Virtual Tree

Introduction

Naive Approach

For the problem above, it is not difficult to see that if the tree has few vertices, we can directly run DP.

First, we call a point selected in a query a key point.

Let $Dp(i)$ denote the minimum cost such that $i$ is not connected to any key point in its subtree.

Let $w(a,b)$ denote the weight of the edge between $a$ and $b$.

Then enumerate the children $v$ of $i$:

• If $v$ is not a key point: $Dp(i)=Dp(i) + \min \{Dp(v),w(i,v)\}$;
• If $v$ is a key point: $Dp(i)=Dp(i) + w(i,v)$.

Good, this gives us an $O(nq)$ program.

Sounds interesting.

Optimized Approach

It is not difficult to see that many vertices are actually useless. Take the following figure as an example:

Suppose the key points we select are:

Only the two red points in the figure are key points, while all the other points are 「non-key points」.

For this problem, we only need to ensure that the red points cannot reach node $1$.

By observing the figure, we can conclude that the right subtree of node $1$ (although there may actually be multiple subtrees, there are only two here, so we temporarily call them this) contains no red nodes, so there is no need to run DP on it.

Looking at the conditions given in the problem, the total number of red points (key points) is of the same order as $n$. In other words, the red points in a single query are very sparse relative to the whole tree, so it would be good if we could make the complexity depend on the number of red points.

Therefore, we need to compress the information and compress a large tree into a small tree.

Virtual Tree Virtual Tree

This leads us to the concept of a virtual tree.

Let us first take an intuitive look at what a virtual tree looks like.

In the figures below, the red vertices are the key points we selected. Both red and black vertices are vertices in the virtual tree. The black edges are edges in the virtual tree.

Because the LCA of any two key points also contains important information that needs to be preserved, we need to preserve their LCAs, so a virtual tree does not necessarily contain only key points.

It is not difficult to see that the ancestor-descendant relationships in the virtual tree do not change. (That is, there will not be any strange situation where $a$ was originally an ancestor of $b$ but later $a$ becomes a descendant of $b$, or something like that.)

But we cannot enumerate LCAs by brute force in $O(k^2)$, so it is natural to think of first sorting the key points by DFS order, then finding the LCA of every two adjacent key points after sorting (where adjacent means that the absolute difference between their indices in the sorted sequence is 1), and adding it to the virtual tree.

Our most urgent task is to determine how to construct the virtual tree.

Before presenting a solution, let us first confirm a fact: in a virtual tree, as long as the ancestor-descendant relationships do not change, nodes can be added arbitrarily.

That is, if we want, we can add every point in the original tree to the virtual tree without causing WA (although it would cause TLE).

Therefore, for convenience, we can first add node $1$ to the virtual tree, which does not affect the answer.

First Construction: Double Sorting + LCA Edges

Because the LCA of multiple nodes may be the same, we cannot add it to the virtual tree multiple times.

A very intuitive method is:

• Sort the key points by DFS order;
• Traverse them once, find the LCA of every two adjacent key points, and remove duplicates;
• Then build the tree according to the ancestor-descendant relationships in the original tree.

In the concrete implementation, enumerate two adjacent numbers in the key-point sequence, find their LCA, and add it to sequence $A$.

Because of the properties of DFS order, sequence $A$ already contains all vertices in the virtual tree at this point, but it may contain duplicates.

Therefore, we sort sequence $A$ by DFS order from small to large and remove duplicates.

Finally, in sequence $A$, enumerate two adjacent vertex numbers $x,y$, find their LCA, and connect $\operatorname{LCA}(x,y),y$; the virtual tree is then constructed.

Why can connecting $\operatorname{LCA}(x,y)$ and $y$ avoid both omissions and duplicates?

Because at least two real points are needed to summon a virtual point, and there is also one root node, the number of vertices in the virtual tree is twice the number of real points.

The time complexity is $O(m\log n)$, where $m$ is the number of key points and $n$ is the total number of points.

Implementation

int dfn[MAXN];
int h[MAXN], m, a[MAXN], len;  // Store key points

bool cmp(int x, int y) {
  return dfn[x] < dfn[y];  // Sort by dfs order
}

void build_virtual_tree() {
  sort(h + 1, h + m + 1, cmp);  // Sort the key points by dfs order
  for (int i = 1; i < m; ++i) {
    a[++len] = h[i];
    a[++len] = lca(h[i], h[i + 1]);  // Insert lca
  }
  a[++len] = h[m];
  sort(a + 1, a + len + 1, cmp);  // Sort all vertices in the virtual tree by dfs order
  len = unique(a + 1, a + len + 1) - a - 1;  // Remove duplicates
  for (int i = 1, lc; i < len; ++i) {
    lc = lca(a[i], a[i + 1]);
    conn(lc, a[i + 1]);  // Add an edge; if there are edge weights, use distance(lc,a[i+1])
  }
}

Actually, this is already sufficient to construct a virtual tree.

Second Construction: Using a Monotone Stack

How do we use a monotone stack to construct a virtual tree?

First, we need to clarify one goal: we want to use a monotone stack to maintain a chain in the virtual tree.

That is, every two adjacent nodes in the stack are also adjacent in the virtual tree, and the stack is monotonically increasing from bottom to top (meaning that the DFS orders of the nodes in the stack are monotonically increasing). Put plainly, the parent of a node is the node immediately below it in the stack.

First, add node $1$ to the stack.

Then add the key nodes in increasing DFS order.

Suppose the LCA of the current node and the top of the stack is the top of the stack. This means that they lie on one chain, so we can simply push the current node onto the stack.

Suppose the LCA of the current node and the top of the stack is not the top of the stack:

At this point, the chain currently maintained by the monotone stack is:

But we need to turn the chain into:

Then we simply pop the nodes marked with dashed lines from the stack. Before popping them, remember to connect each of them to its parent in the virtual tree.

If we find after popping that the top of the stack is not the LCA, we need to push the LCA onto the stack.

Then push the current node onto the stack.

Here is a concrete example. Suppose we want to build a virtual tree for nodes 4, 6, and 7 of the following tree:

The steps are as follows:

• Sort the 3 key points $6,4,7$ by DFS order to obtain the sequence $[4,6,7]$.
• Push $1$ onto the stack.

We use red points to represent points in the stack, and cyan points to represent points popped from the stack.

• Take the first point in the sequence as the current node, namely $4$. Then take the top element of the stack, namely $1$. Find the LCA of $1$ and $4$: $LCA(1,4)=1$.
• We find that $LCA(1,4)=$ the top element of the stack, which means they lie on one chain of the virtual tree, so we directly push the current node $4$ onto the stack. The current stack is $4,1$.

• Take the second point in the sequence as the current node, namely $6$. Then take the top element of the stack, namely $4$. Find the LCA of $6$ and $4$: $LCA(6,4)=1$.
• We find that $LCA(6,4)\neq$ the top element of the stack, so enter the checking stage.
• Checking stage: we find that the DFS order of the top node $4$ is greater than that of $LCA(6,4)$, but the DFS order of the next-largest node (the node immediately below the top node in the stack) $1$ is equal to that of the LCA (in fact, equal DFS orders mean that the nodes are also equal). This means that the LCA has already been pushed onto the stack, so we directly connect the edge $1\to4$, namely the edge from the LCA to the top element of the stack, and pop $4$ from the stack.

• The checking stage is over. Push $6$ onto the stack; the current stack is $6,1$.

• Take the third point in the sequence as the current node, namely $7$. Then take the top element of the stack, namely $6$. Find the LCA of $7$ and $6$: $LCA(7,6)=3$.
• We find that $LCA(7,6)\neq$ the top element of the stack, so enter the checking stage.
• Checking stage: we find that the DFS order of the top node $6$ is greater than that of $LCA(7,6)$, but the DFS order of the next-largest node (the node immediately below the top node in the stack) $1$ is less than that of the LCA. This means that the LCA has not yet been pushed onto the stack, so we directly connect the edge $3\to6$, namely the edge from the LCA to the top element of the stack. Pop $6$ from the stack, and push $LCA(6,7)$ onto the stack.
• The checking stage is over. Push $7$ onto the stack; the current stack is $1,3,7$.

• We find that all 3 nodes in the sequence have already been pushed onto the stack, so exit the loop.
• There are still 3 nodes in the stack: $1,3,7$. It is obvious that they lie on one chain, so directly connect the edges $1\to3$ and $3\to7$.
• The virtual tree is now complete!

Next, we delete the points that were never pushed onto the stack (the non-cyan points); the virtual tree then looks like this:

There are many details here. For example, if we store the virtual tree using an adjacency list, we need to clear the adjacency list. However, clearing the entire adjacency list directly is slow, so we only need to clear the adjacency list corresponding to an element when an element that has never been pushed onto the stack is pushed onto the stack.

The time complexity is also $O(m\log n)$ (because of sorting), where $m$ is the number of key points and $n$ is the total number of points.

Implementation

The C++ code for building a virtual tree looks roughly like this:

bool cmp(const int x, const int y) { return id[x] < id[y]; }

void build() {
  sort(h + 1, h + k + 1, cmp);
  sta[top = 1] = 1, g.sz = 0, g.head[1] = -1;
  // Push node 1 onto the stack, clear the adjacency list corresponding to node 1, and set the number of adjacency-list edges to 0
  for (int i = 1, l; i <= k; ++i)
    if (h[i] != 1) {
      // If node 1 is a key point, do not add it again
      l = lca(h[i], sta[top]);
      // Calculate the LCA of the current node and the top of the stack
      if (l != sta[top]) {
        // If the LCA differs from the top element, the current node is not on the chain stored in the current stack
        while (id[l] < id[sta[top - 1]])
          // The DFS order of the next-largest node is greater than the DFS order of the LCA
          g.push(sta[top - 1], sta[top]), top--;
        // Connect and pop the part of the chain that does not overlap the chain containing the current node
        if (id[l] > id[sta[top - 1]])
          // If the LCA is not the next-largest node (here, greater is equivalent to not equal)
          g.head[l] = -1, g.push(l, sta[top]), sta[top] = l;
        // This means the LCA is pushed onto the stack for the first time: clear its adjacency list, add the edge, pop the stack top, and push the LCA
        // onto the stack
        else
          g.push(l, sta[top--]);
        // This means the LCA is the next-largest node, so simply pop the stack top
      }
      g.head[h[i]] = -1, sta[++top] = h[i];
      // The current node must be pushed onto the stack for the first time, so clear its adjacency list and push it onto the stack
    }
  for (int i = 1; i < top; ++i)
    g.push(sta[i], sta[i + 1]);  // Connect the remaining final chain
  return;
}

Thus, we have learned how to build a virtual tree!

For the Battle of Attrition problem, we can directly run the DP described at the beginning on the virtual tree. In effect, the virtual tree eliminates those useless non-key vertices! We still consider all children $v$ of $i$:

• If $v$ is not a key point: $Dp(i)=Dp(i) + \min \{Dp(v),w(i,v)\}$
• If $v$ is a key point: $Dp(i)=Dp(i) + w(i,v)$

Thus, this problem is easily solved.

Recommended Problems

• 「SDOI2011」 Battle of Attrition
• 「HEOI2014」 Major Project
• CF613D Kingdom and its Cities
• 「HNOI2014」 World Tree