Editorial: Graph Cutting (Three Vertices, Any Size)
This extends E0 from two pinned vertices to three. The mandatory core becomes the Steiner tree $T(a,b,c)$ instead of a single path.
In a tree, the minimal connected set containing $a,b,c$ is unique:
$$T(a,b,c)=P(a,b)\cup P(b,c)\cup P(a,c).$$Two shapes:
- Path type: one vertex lies on the path between the other two; $T$ is a simple path.
- Fork type: three branches meet at a center $r$; $T$ looks like a tripod.
Any connected $S$ with $\{a,b,c\}\subseteq S$ must contain $T(a,b,c)$.
Root the side logic at $T$. For $v\in T$ and a neighbor $x\notin T$, any optional vertices lie in $x$’s subtree and must stay connected through $x$. Define $\mathrm{ways}(u)$ as in E0:
$$\mathrm{ways}(u)=\prod_{\text{side child }c}\bigl(1+\mathrm{ways}(c)\bigr),\qquad \mathrm{ways}(\text{leaf})=1.$$Independent factors at different attachment points give
$$\boxed{\ \#S=\prod_{\substack{v\in T(a,b,c)\\ x\in N(v)\setminus T}}\bigl(1+\mathrm{ways}(x)\bigr)\ }.$$- Mark vertices of $T$ by tracing $P(a,b)$, $P(b,c)$, $P(a,c)$ (three BFS/DFS path walks).
- For each $v\in T$, each neighbor $x\notin T$, multiply by $1+\mathrm{ways}(x)$.
| Step | Cost |
|---|---|
| Three path markings ($P(a,b)$, $P(b,c)$, $P(a,c)$) | $O(n)$ each, $O(n)$ total with three BFS |
Side DP ways(x) on off-$T$ subtrees |
$O(n)$ total |
| Product over attachment points | $O(n)$ |
Time: $O(n)$ per test case — same asymptotics as E0, with a constant factor $\approx 3$ for the extra path walks.
Space: $O(n)$.
$\sum n \le 2000$ → $O\!\left(\sum n\right)$ total for E3 (one fixed triplet per test). Same as E0: linear per query, not $O(n^2)$ unless you iterate all triples.
| Version | Time per test | Scope |
|---|---|---|
| E0 | $O(n)$ | one fixed pair |
| E3 | $O(n)$ | one fixed triplet |
| E4 | $O(n d^2)$ worst case | one fixed triplet |
| E | $O(n^2)$–$O(n^3)$ | all triples |
| Triple | $T$ | Side branches | Answer |
|---|---|---|---|
| $(1,2,3)$ | path $2\text{–}1\text{–}3$ | leaf $4$ off $1$ | $2$ |
| $(2,3,4)$ | whole tree | none | $1$ |
| Step | Problem | Core | Count | Time |
|---|---|---|---|---|
| E0 | pair, any size | path $P(a,b)$ | all supersets | $O(n)$ |
| E1 | pair, size $d$ | path | supersets of size $d$ | $O(n d^2)$ |
| E2 | all pairs | minimal = path | valid pairs | $O(n^2)$ |
| E3 | triplet, any size | $T(a,b,c)$ | all supersets | $O(n)$ |
| E4 | triplet, size $d$ | $T(a,b,c)$ | supersets of size $d$ | $O(n d^2)$ |
| E | all triples | minimal = $T$ | valid triples | $O(n^2)$ intended |
See model solution.