Editorial: Graph Cutting (Three Vertices, Fixed Size)

Extends E3 with a size constraint, exactly as E1 extends E0. The core is $T(a,b,c)$ with $L=|T(a,b,c)|$ vertices.

Reduction

Every valid $S$ satisfies $T(a,b,c)\subseteq S$ and $|S|=d$, so

$$|S| = L + t,\qquad t = d - L$$

where $t$ counts vertices taken from side branches off $T$. If $d

Size polynomials (same as E1)

For side root $x$:

$$F_x(z)=z\cdot\prod_{y}\bigl(1+F_y(z)\bigr).$$

At $v\in T$ with side neighbors $x_1,\ldots,x_m$:

$$G_v(z)=\prod_i\bigl(1+F_{x_i}(z)\bigr).$$

Overall:

$$G(z)=\prod_{v\in T} G_v(z),\qquad \text{answer}=[z^{d-L}]\,G(z).$$

Use conv_skip from the E1 solution: multiply by $(1+F)$ via “skip ($+a[i]$) or take ($+a[i]\cdot b[j]$ for $j\ge 1$)”.

Complexity

Per test case

Same structure as E1, with $L = |T(a,b,c)|$:

Step	Cost
Mark $T(a,b,c)$ (three paths)	$O(n)$
Side size DP + `conv_skip`	$O(n d^2)$ worst case
Read coefficient $[z^{d-L}]$	$O(d)$

Space: $O(n + d)$.

All test cases

One fixed triplet per test, $\sum n \le 2000$. Same as E1: $O(n d^2)$ per query in theory, often $O(n)$ when the Steiner core has no side branches.

Comparison

Version	Time per test	Scope
E1	$O(n d^2)$ worst case	one fixed pair
E4	$O(n d^2)$ worst case	one fixed triplet
Brute all triples via E4	$O(n^3 d^2)$	too slow for $n = 2000$
E	$O(n d)$ v2 / $O(n^2)$–$O(n^3)$ v1	batch all triples

Bridge to E

Setting	What you count	Method
E4 (here)	Supersets of size $d$ for one triple	Steiner core + size DP
E	Triples whose minimal cut has size $d$	Root at each $r$; fork triples via depth histograms + pair DP; path triples via longest paths

When Fedya takes the minimal subgraph, $|S|=|T(a,b,c)|$ exactly — no extras. E4 counts richer families; E4’s polynomial machinery (convolutions over branch statistics) becomes depth convolutions in E.

Trick 7 connection (blog entry 100910)

Identical to E1: conv_skip on side subtrees is Trick 7’s sequential sibling merge with vector length $\le d$, so side work is $O(n d)$ (the $O(nk)$ generalization with $k=d$), not cubic in subtree size.

See model solution.

Knapsack on Steiner tree + small-to-large (model_sol_opt)

Same three tricks as E1’s optimized version:

cap side merges at $\mathrm{need} = d - L$;
knapsack DP over Steiner vertices (in fixed order) instead of one big product polynomial;
smallest-first sibling merges inside each side subtree.

Complexity per query: $O(n \cdot \mathrm{need} + L \cdot \mathrm{need}^2)$ with $\mathrm{need} \le d$.

See the Knapsack on Steiner tree + small-to-large block in code.