Editorial: Graph Cutting (Two Vertices, Fixed Size)

After E0 (count all connected supersets of $\{a,b\}$), we restrict to $|S|=d$. This is the main technical step before E2 (all pairs, minimal subgraph) and E (three vertices).

Let $P(a,b)$ have $L$ vertices. Every valid $S$ contains $P(a,b)$, so

where $t \ge 0$ is the number of vertices taken from side branches (subtrees hanging off the path, not on it). We need $t = d - L$; if $d < L$, answer $0$.

For a side vertex $x$, define

where $\mathrm{ways}_s(x)$ counts connected subsets of $x$’s subtree that contain $x$ and have size $s$.

Leaf: $F_x(z)=z$.

Recursion: process side children $y$ of $x$. Each child is skipped ($1$) or contributes $F_y(z)$:

Implementation: start cur[1]=1, for each child cur = conv_skip(cur, child) where conv_skip multiplies by $(1+F_y)$ — copy coefficients (skip) plus shift-convolve (take).

At $v \in P(a,b)$, branches are independent:

Again use conv_skip for each factor $(1+F_x)$.

Side regions at different path vertices are disjoint:

Answer: coefficient of $z^{d-L}$ in $G(z)$.

Star center $1$, leaves $2,3,4$; $a=2$, $b=3$, $d=4$.

• Path length $L=3$.
• Side branch at $1$: $F_4(z)=z$, so $G_1(z)=1+z$.
• Need $d-L=1$ extra vertex: coefficient of $z^1$ is $1$ → unique set $\{2,1,3,4\}$.

For $d=3$: need $z^0$ coefficient → only $1$ way without $4$ → $\{2,1,3\}$.

Time: $O(n d^2)$ per test case in the worst case (each conv_skip is $O(d^2)$, up to $O(n)$ side attachments). With $n, d \le 2000$ that is $O(8 \cdot 10^9)$ in theory, but on typical trees (long Steiner path, few side branches) it is much faster — often $O(n)$ after marking the core.

Space: $O(n + d)$.

$\sum n \le 2000$ caps the input size. E1 is one fixed pair per test, so you are not paying $O(n^2)$ unless you loop over all pairs yourself (E2 does, and needs $O(n^2)$).

The polynomial / convolution machinery from E1 reappears in E when you track depths from a root instead of sizes from side branches.

Side-branch conv_skip merges children one at a time:

Each merge loops over indices of two vectors whose lengths are bounded by subtree size (or by $d$ after restricting to size $\le d$). That is exactly the sequential sibling merge from Trick 7 / Miss Punyverse: total work $O(n^2)$ on the side tree, or $O(n d)$ with the $O(nk)$ cap $k = d$.

See model solution.

Two further optimizations on top of the baseline DP:

1. Cap at $\mathrm{need} = d - L$. Side-branch conv_skip only needs degrees up to $\mathrm{need}$; truncate after every merge.

2. Knapsack on the mandatory path. Instead of multiplying full polynomials along $P(a,b)$, keep $\mathrm{dp}[s]$ = number of ways to allocate exactly $s$ extra vertices from the processed prefix. Update with the capped branch polynomial at each path vertex — $O(L \cdot \mathrm{need}^2)$ instead of growing a degree-$(\mathrm{need})$ polynomial explicitly.

3. Small-to-large sibling merge. When a side vertex has several off-path children, merge their capped polynomials smallest first so intermediate vectors stay short (same Trick 7 idea as Miss Punyverse).

With $\mathrm{need} \le d$, this is $O(n d + L d^2)$ per query — much better on typical trees when the path is short or $\mathrm{need} \ll d$, but still $O(n d^2)$ in the adversarial worst case (see NTT section below).

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

See the O(n d log d) via Atcoder NTT block in code for model_sol_ntt.cpp.

The $O(n d^2)$ worst case comes entirely from naive polynomial multiplication at degree $\mathrm{need} \le d$:

• Each capped conv_skip_cap costs $O(\mathrm{need}^2)$.
• There are $O(n)$ such merges over side edges plus $O(L)$ path knapsack updates, each $O(\mathrm{need}^2)$ when done naively.

Replace every multiply of two capped polynomials with Atcoder Library NTT (#include <atcoder/convolution>, atcoder::convolution on modint998244353 coefficients). A single multiply of degree $\le d$ then costs $O(d \log d)$.

If side polynomial $F$ has $F(0)=0$, then conv_skip(a, F) is multiplication by $(1+F(z))$. Build

and set nxt = convolution(a, c), then truncate to length $\mathrm{need}+1$. Same mod $998244353$ as the answer.

At path vertex $v$, instead of the double loop over $s,t$:

(keep only the first $\mathrm{need}+1$ coefficients).

Since $L \le n$ and $\mathrm{need} \le d$, the whole test case is $O(n d \log d)$ in the worst case.

• Use the same mint = modint998244353 as the rest of the tutorial chain; ACL convolution expects that modulus.
• NTT has larger constants than naive $O(d^2)$ for small degrees. A hybrid (naive below a threshold, NTT above) is fine for speed; all NTT is what gives the $O(n d \log d)$ worst-case proof.
• This does not beat $O(n d \log d)$ within the generating-function DP: you still perform $\Theta(n)$ convolutions of degree $\Theta(d)$ on adversarial trees (long path, every side branch a full degree-$d$ factor).
• The same idea applies to E4 (Steiner core instead of a path); E2 has no polynomial merges.