Hints: Graph Cutting (Two Vertices, All Pairs)
This is the pair analogue of E: Fedya picks $(a,b)$ and cuts the minimal connected subgraph, not an arbitrary superset. Warmups E0/E1 count supersets; this problem counts valid pairs under Fedya’s rule.
Two vertices $a,b$ in a tree: how many minimal connected subgraphs contain both? What subgraph is it?
Answer to Hint 1: Exactly one — the unique simple path $P(a,b)$. So “minimal cut size $d$” means $|P(a,b)|=d$.
If $P(a,b)$ has $d$ vertices, how many edges does it use? Relate $d$ to $\mathrm{dist}(a,b)$.
Answer to Hint 3: A path with $d$ vertices has $d-1$ edges, so $\mathrm{dist}(a,b)=d-1$.
Restate the problem without “subgraphs”: count unordered pairs $(a,b)$ with $a \lt b$ and $\mathrm{dist}(a,b)=d-1$.
Answer to Hint 5: Yes. Example 1 (star, $d=3$): three leaf–leaf pairs, each at distance $2$.
With $\sum n \le 2000$, is $O(n^2)$ acceptable? Describe a simple algorithm: fix $a$, BFS distances, count $b \gt a$ with $\mathrm{dist}(a,b)=d-1$.
Answer to Hint 7: Yes — at most about $4 \cdot 10^6$ BFS edge relaxations total. Sum over $a=1..n$, run BFS, add $1$ for each $b \gt a$ at distance $d-1$.
Relation to E1. E1 counts connected supersets of fixed $(a,b)$ with size $d$. This problem uses the minimal subgraph (path only). When $d=L=|P(a,b)|$, E1 counts how many supersets of size exactly $d$ exist — often $1$, but can be more if side branches allow extras while staying at size $d$. Why doesn’t Fedya’s rule care about those E1 counts?
Answer to Hint 9: Fedya always cuts the minimum connected subgraph, not any superset. Valid pairs are determined solely by path length. E1’s machinery (side-branch polynomials) prepares you for E, where three vertices create a non-path Steiner tree.
Preview of E. With three vertices, the minimal subgraph can be a path (two leaves on a line) or a fork (three branches meeting at a center). E2 has only the path case. What new configuration appears with three vertices?
Answer to Hint 11: A “tripod”: a center vertex $r$ with three vertices in three different subtrees (or two in one branch and one in another with $r$ on the Steiner tree). Counting those fork configurations uses depth histograms and convolutions — the same spirit as E1’s size polynomials, but with depths from a root.