Editorial: Graph Cutting

This is the final step of the Graph Cutting tutorial: count all triples under Fedya’s rule. Work through the chain if you have not already:

Pairs: E0 (fixed pair, any size) → E1 (fixed size) → E2 (all pairs, minimal cut).

Triplets: E3 (fixed triplet, any size) → E4 (fixed size) → E (all triples, minimal cut).

Count triples $1\le aminimal connected subgraph containing $a,b,c$ has exactly $d$ vertices.

That minimal subgraph is the Steiner tree $T(a,b,c)$, so we need $|T(a,b,c)|=d$.

Unlike E3/E4, we do not allow extra vertices beyond $T$.

All three vertices lie on one simple path of $d$ vertices $v_0,\ldots,v_{d-1}$. Then $|T(a,b,c)|=d$ iff the smallest and largest indices among the three are $0$ and $d-1$. For each such path, there are $d-2$ valid triples (choose the middle vertex freely among interiors).

Counting paths: From each node, DFS each child subtree tracking depth. When depth reaches $d-1$, a path of $d$ vertices ending here is found; add $d-2$. Each undirected path is counted twice (from both ends) → divide total by $2$. This is the dub/2 term in the model solution.

Three vertices live in three different child subtrees of some center $r$. If their depths from $r$ are $d_1,d_2,d_3$,

Fix $r$ as the branch point. For each child $c$ of $r$, build histogram $x[t]$ = number of vertices at depth $t$ in $c$’s subtree ($t\ge 1$).

Process child histograms in increasing size. Maintain:

• dp[0][j] — cumulative vertex-count histogram from processed subtrees (sum of $x$’s).
• dp[1][k] — count of pairs of vertices from two distinct processed subtrees with combined statistic $k$ (built by dp[1][i+j+1] += dp[0][j] * x[i] before merging $x$ into dp[0]).

When a third histogram $x$ arrives, complete triples:

Then merge $x$ into dp[0] and update dp[1] for future triples.

Loop $r=1..n$, sum fork contributions, add dub/2 for path triples.

• Path triples: unique containing path of length $d$; counted exactly once in dub/2.
• Fork triples: unique lowest vertex $r$ where the three directions to $a,b,c$ lie in three different child subtrees of $r$; counted when processing that $r$ and that ordered triple of branches.

Path and fork cases are disjoint.

The limits are $n \le 2000$, $\sum n \le 2000$ over the whole input. The largest test has $n = 2000$, so you should target $O(n^2)$ per test case — about $4 \cdot 10^6$ primitive operations. Anything $O(n^3)$ with $n = 2000$ ($\sim 8 \cdot 10^9$) can still pass in C++ if the inner loop is tiny (the model solution does), but $O(n^2)$ is the right design goal.

For each of $n$ roots, DFS each child subtree once. Each vertex is scanned once per root, so $O(n^2)$ total for building histograms and counting path triples.

For root $r$, let $h_1, h_2, \ldots$ be the depth histogram lengths in its child subtrees (each $h_i \le n$). Merging two branches costs $O(h_i \cdot h_j)$ in the model code (nested loops over histogram indices), not merely $O(d^2)$ unless you cap at depth $d$.

• Low degree (star, tripod): $h_i = O(1)$ or $O(d)$ with few branches → $O(n d^2)$ or less per root, $O(n^2)$ over all roots in practice.
• Long path: an internal root splits the path into two arms of lengths $\Theta(n)$; one merge costs $\Theta(n^2)$; summed over $\Theta(n)$ roots → $O(n^3)$ worst-case fork work (the path-only case still finishes in $\sim 0.2\,\mathrm{s}$ for $n = 2000$ in the model solution).

Space: $O(n + d)$ — adjacency list plus histogram/DP vectors of length $O(\min(n,d))$ per root (reused).

Because $\sum n \le 2000$, even $O(n^3)$ on one test with $n = 2000$ is the only hard case; the rest are tiny.

Design pattern: “all pairs/triples” versions (E2, E) require $\Omega(n^2)$ — you cannot beat quadratic in $n$ if you re-root or BFS from every vertex. Fixed-pin warmups (E0–E1, E3–E4) are $O(n)$ or $O(n d^2)$ per query.

The first model solution (model_sol.cpp) re-roots at every vertex and DFS-es full child subtrees even when depth $\ge d$, so fork merges can blow up to $O(n^3)$ on a path. The v2 solution fixes this and matches the $O(nk)$ generalization of Trick 7 with $k = d$.

1. Cap depth at $d$. Vertices deeper than $d-1$ from a branch center cannot belong to a minimal cut of size $d$. Every DFS / histogram has length $\le d$.

2. Path triples separately in $O(n d)$: BFS from each $s$ only until depth $d-1$; for each $v$ at distance $d-1$, add $(d-2)$; divide by $2$ for unordered triples on that path.

3. Fork triples at each branch center $r$: build one depth histogram per neighbor direction, scanning only to depth $d-1$. Merge histograms with the same dp[0] / dp[1] sequential sibling merge as v1.

With $d \le n \le 2000$, $O(n d) = O(n^2)$ and $O(n d^2) = O(n^3)$ in the worst case — but when $d \approx n$ on a path, fork triples are $0$ and only the $O(n d)$ path phase runs. The v2 path phase alone replaces v1’s $O(n^2)$ full-subtree dub scans with $O(n d)$ capped BFS (same when $d \sim n$, strictly better when $d \ll n$).

Trick 7 applies directly to the sequential sibling merge (same shape as Miss Punyverse in the blog): each inner merge pairs indices from two different branches; with vector length $\le k = d$, the $O(nk)$ bound controls fork work on low-degree trees. E1/E4 side-branch conv_skip is the same merge pattern on size instead of depth.

See model_sol_v2.cpp in the $O(n^2)$ version (Trick 7) expand block.

v2 already caps branch histograms at depth $d$. The remaining fork work at center $r$ is a sequential sibling merge of those histograms — the same Trick 7 pattern as E1/E4 side branches.

v3 sorts the per-neighbor histograms by length and merges smallest first, so intermediate vectors stay as short as possible. Asymptotics unchanged ($O(n d^2)$ fork merges summed over centers), but constants improve on high-degree branch points.

See the Small-to-large fork merge block in code.

E4 fixes $(a,b,c)$ and counts supersets of size $d$ via size polynomials on side branches. E counts triples for the minimal core only. The fork-type root DP is the batch version of “pick one vertex from each of three branches with a combined depth budget” — the same convolution spirit as E4, but with depth histograms and without a Steiner core plus extras.

See model solution.