Hints: Statistics on Tree

First ignore efficiency. For a fixed pair $(u,v)$, what are the components after deleting all edges on the path from $u$ to $v$?

Answer to Hint 1: Every vertex on the path may keep some side subtrees attached to it. The components are exactly those side parts, plus the two endpoint sides.

So a brute force solution can try every pair, mark the path, and find the largest remaining component. This is much too slow, but it tells us what has to be counted.

Can we make the value of a pair easier to describe by rooting the tree?

Answer to Hint 3: Root the tree somewhere. If the path between two vertices goes down into one child subtree of a vertex $x$, then deleting the first edge into that child separates a component of size equal to that child subtree.

If the path goes through two child subtrees of $x$, the component on the “outside” of these two subtrees has size $n-a-b$, where $a$ and $b$ are the two child-subtree sizes.

What root should we choose so that most of these “outside” components are guaranteed to be the largest component?

Answer to Hint 5: Choose a centroid as the root.

Then every subtree hanging away from the centroid has size at most $n/2$. In particular, for any non-centroid vertex, its whole rooted subtree has size at most $n/2$.

Suppose the path has lowest common ancestor $x$, and $x$ is not the centroid. Why is the outside part the largest component?

Answer to Hint 7: If the path uses one child subtree of $x$ with size $a$, the outside component has size $n-a$.

If it uses two child subtrees with sizes $a$ and $b$, the outside component has size $n-a-b$. Since the entire subtree of $x$ has size at most $n/2$, we have $a+b < n/2$, so $n-a-b > n/2$. Every hanging component inside those child subtrees has size at most $a$ or $b$, hence is smaller.

Using the previous hint, how can we count all pairs whose lowest common ancestor is a fixed vertex $x$?

Answer to Hint 9: Let the child-subtree sizes of $x$ be $s_1,s_2,\ldots$.

For pairs $(x,v)$ with $v$ in child subtree $s_i$, add $s_i$ pairs to answer value $n-s_i$.

For pairs with endpoints in two different child subtrees $s_i$ and $s_j$, add $s_i s_j$ pairs to answer value $n-s_i-s_j$.

The model solution groups equal subtree sizes with a frequency array so this pair counting is not quadratic in the degree when many sizes repeat.

What about pairs $(v,v)$?

Answer to Hint 11: If $u=v$, no edge is removed. The whole tree remains one component, so the value is $n$.

Therefore answer value $n$ gets $n$ pairs immediately.

Where can the counting from Hint 10 be wrong?

Answer to Hint 13: Only when the lowest common ancestor is the centroid itself.

Let $L$ be the largest child subtree of the centroid, with size $A$. If a pair has one endpoint in $L$ and the other endpoint in another centroid child subtree, then the largest remaining component might be on the $L$ side, not on the outside side $n-A-b$.

So first subtract the naive contribution $A\cdot b$ from answer value $n-A-b$ for every other centroid child subtree of size $b$.

Answer to Hint 14: For the corrected centroid-crossing pairs, compute one number for each possible endpoint.

For a vertex $v$ inside the largest centroid branch $L$, define $f(v)$ as the largest component that can appear on the $L$ side when the path goes from $v$ up to the centroid. This is the maximum of:

• $\mathrm{sz}(v)$;
• for each ancestor step on the path, the part of that ancestor subtree not going toward $v$.

For a vertex $w$ in any other centroid branch, define $g(w)$ similarly, but also include the component at the centroid after removing both the largest branch and $w$’s branch.

Then every corrected pair has value $\max(f(v),g(w))$. Sort all $f$ values and all $g$ values, and merge the two sorted arrays to count how many pairs have each maximum.