Editorial: Graph Cutting (Two Vertices, All Pairs)

This problem is the pair version of E. Graph Cutting: same Fedya rule, two vertices instead of three. Read E0 and E1 first if you want the superset-counting warmups; this page is the direct analogue of the full statement.

Minimal subgraph on two vertices

In a tree, the smallest connected set containing $a$ and $b$ is unique: the path $P(a,b)$. Therefore

$$\text{Fedya’s cut size}=|P(a,b)|=\mathrm{dist}(a,b)+1.$$

We need $|P(a,b)|=d$, i.e.

$$\mathrm{dist}(a,b)=d-1.$$

Algorithm

Count unordered pairs with graph distance $d-1$:

ans = 0
for s = 1 .. n:
    BFS from s, get dist[·]
    for t = s+1 .. n:
        if dist[t] == d-1: ans++

With $\sum n \le 2000$, $O(n^2)$ is enough ($O(n(n+m))$ per test case).

Examples (same trees as E)

Star ($n=4$, $d=3$): three leaf pairs, each distance $2$ → answer $3$.

Second sample ($n=5$, $d=5$): longest path has $4$ vertices (e.g. $3 \text{–} 2 \text{–} 1 \text{–} 5$). No pair has distance $4$ → answer $0$. (E still gives $1$ from triple $(3,4,5)$ whose Steiner tree is the whole tree.)

E0 / E1 vs E2

Problem	Rule	What you count
E0	Any connected superset of $\{a,b\}$	All such $S$
E1	Superset, $\\|S\\|=d$	Subsets of size $d$
E2	Minimal subgraph, size $d$	Pairs with $\mathrm{dist}=d-1$
E	Minimal subgraph, size $d$	Triples (path + fork Steiner trees)

E1’s side-branch DP is not needed for E2, but the convolution idea returns in E for combining depths in three different branches.

Optional faster counting

An edge-splitting idea (count pairs at distance $d-1$ through each edge) only works if each unordered pair is attributed to one edge; on a long path the same pair is counted on every edge of its path. Do not use that without a tie-break rule.

$O(n^2)$ version — Trick 7 (model_sol_v2)

Key change: BFS from each source stops expanding at depth $d-1$.

for s = 1 .. n:
    BFS from s, do NOT push neighbors when dist = d-1
    for t > s with dist[t] = d-1: ans++

Version	Time	Notes
v1 (`model_sol.cpp`)	$O(n^2)$	full BFS each source
v2 (`model_sol_v2.cpp`)	$O(n d)$	capped BFS; $O(n^2)$ when $d \le n$

When $d \ll n$ this is strictly faster than v1; when $d \approx n$ it is the same order. Under contest limits ($n, d \le 2000$), $O(n d)$ is $O(n^2)$.

This is the $O(nk)$ specialization of Trick 7 with $k = d$: scan only the first $k$ layers from each root instead of the whole tree.

See the $O(n^2)$ version (Trick 7) block in code.

Complexity

What you need to pass

$\sum n \le 2000$ → largest test has $n = 2000$. You must stay around $O(n^2)$ ($\sim 4 \cdot 10^6$). The model BFS-from-every-source solution is $\Theta(n^2)$ on a tree and is the right complexity class.

Per test case

Approach	Time	Notes
BFS from every source (v1)	$O(n^2)$	$n$ full BFS traversals
Capped BFS (v2, Trick 7)	$O(n d)$	stop at depth $d-1$; $O(n^2)$ when $d \le n$
Brute via E1 on all pairs	$O(n^3 d^2)$	too slow

Space: $O(n)$.

All test cases

$O\!\left(\sum n_i^2\right)$; with $\sum n \le 2000$ the worst case is one test with $n = 2000$ → $O(4 \cdot 10^6)$.

See model solution.