Editorial: Graph Cutting (Two Vertices, Any Size)

This is step 1 of the E tutorial chain: count connected subgraphs with two pinned vertices. Next: E1 adds a size constraint; E2 counts valid pairs (the direct analogue of the full problem with triples).

Problem recap

Given a tree and distinct vertices $a,b$, count connected vertex sets $S$ with $\{a,b\}\subseteq S$.

Key observation: the path is forced

In a tree there is a unique simple path $P(a,b)=v_0,v_1,\ldots,v_k$ with $v_0=a$, $v_k=b$. If $S$ is connected and contains $a,b$, then $P(a,b)\subseteq S$. So every valid $S$ equals the path plus optional extra vertices hanging off it.

Side branches factorize

Fix $v_i$ on the path. Let $x$ be a neighbor of $v_i$ with $x\notin P(a,b)$. Any valid choice inside $x$’s subtree is either:

empty — do not use that branch ($1$ way), or
non-empty connected — must include $x$ and stay connected to $v_i$.

Define $\mathrm{ways}(u)$ as the number of connected subsets of $u$’s subtree that contain $u$:

$$\mathrm{ways}(u)=\prod_{\text{child }c}\bigl(1+\mathrm{ways}(c)\bigr).$$

(Children are taken in the subtree rooted at $u$ after removing the parent edge; only side subtrees off the path are evaluated.)

Branches at different neighbors of the same $v_i$ are independent, and vertices on different path positions never interact except through the mandatory path. Therefore

$$\boxed{\ \#S=\prod_{i=0}^{k}\ \prod_{\substack{x\in N(v_i)\\ x\notin P(a,b)}}\bigl(1+\mathrm{ways}(x)\bigr)\ }.$$

Example (star with $a=2$, $b=3$)

Path: $2 \text{–} 1 \text{–} 3$ (length $2$). Only side branch is leaf $4$ off center $1$: $\mathrm{ways}(4)=1$, factor $(1+1)=2$. Answer $2$: with or without vertex $4$.

Complexity

Per test case

Step	Cost
BFS from $a$ to recover $P(a,b)$	$O(n)$
Side DP `ways(x)` on each off-path subtree	$O(n)$ total (each vertex visited once)
Multiply factors at path vertices	$O(n)$ (one pass over edges incident to the path)

Time: $O(n)$ per test case.

Space: $O(n)$ for adjacency list, parent/path marks, and recursion stack.

All test cases

With $\sum n \le 2000$, total time is $O\!\left(\sum n\right)$ per file for E0 — at most one pass per vertex across all tests. This is not the same as the $O(n^2)$ budget needed by E2 / E, which count all pairs/triples.

Comparison

Version	Time per test	Notes
E0	$O(n)$	one fixed pair
E1	$O(n d^2)$ worst case	one fixed pair
E2	$O(n^2)$	all pairs — needs quadratic scan

What you learn for later

Idea	Reused in
Path between pinned vertices is mandatory	E1, E, E2
Side subtrees contribute independently via $(1+\mathrm{ways})$	E1 (with sizes), E (with depths)
Tree DP on “connected block containing root of branch”	E1, E

See model solution for the implementation.