Hints: Graph Cutting

Two vertices: minimal connected subgraph = unique path. What is the minimal connected subgraph for three vertices $a,b,c$ in a tree?

Answer to Hint 1: The Steiner tree $T(a,b,c)=P(a,b)\cup P(b,c)\cup P(a,c)$ — exactly the core from E3. Fedya’s cut has size $|T(a,b,c)|$, not a larger superset.

Name the two possible shapes of $T(a,b,c)$. When is it a path? When is it a tripod (one center, three branches)?

Answer to Hint 3: Path type: one vertex lies between the other two on a line. Fork type: the three pairwise paths meet at a single branch point $r$ with three disjoint directions to $a,b,c$.

Restate the problem: count triples $aE2 fit in as the two-vertex case?

Answer to Hint 5: E2 counts pairs with $|P(a,b)|=d$. Here $|T(a,b,c)|=d$; path-type triples are one case, fork-type another.

Path-type triples. Three vertices on one simple path of $d$ vertices: when is $|T(a,b,c)|=d$? If the path is $v_0,\ldots,v_{d-1}$, which triples (by index) use the full $d$ vertices?

Answer to Hint 7: The smallest and largest index among the three must be $0$ and $d-1$ (the outer endpoints). The middle index is any of the $d-2$ interior vertices → $d-2$ triples per path of length $d$.

How many simple paths of $d$ vertices does a tree have? Fix an endpoint $u$ and run DFS: when depth reaches $d-1$, you found one path — but each undirected path is counted twice. How does the model solution’s dub term relate?

Answer to Hint 9: From each oriented endpoint, depth-$d-1$ nodes mark paths; add d-2 per hit. Sum over all roots/endpoints and divide by $2$ for undirected paths. This covers all path-type valid triples.

Fork-type triples. Fix a center vertex $r$. Pick one vertex from each of three different child subtrees at depths $d_1,d_2,d_3$ (distance from $r$). What equation must the depths satisfy so $|T|=1+d_1+d_2+d_3=d$?

Answer to Hint 11: Need $d_1+d_2+d_3=d-1$. Each subtree contributes a histogram $\mathrm{cnt}[t]$ = number of vertices at depth $t$ from $r$.

Process child subtrees of $r$ one by one. Let dp[0][j] accumulate histogram counts from processed branches; let dp[1][k] count ordered pairs of vertices from two different processed branches with combined depth statistic $k$ (see model solution merge dp[1][i+j+1] += dp[0][j]*x[i]). When a third branch $x$ arrives, how do you form a triple with total size $d$?

Answer to Hint 13: For each pair statistic $j$ in dp[1], pick depth need = d - j in the new branch: add x[need] * dp[1][j]. Then merge the new branch into dp[0] and update dp[1] for later triples. Sort branches by histogram size for efficiency.

Final assembly. Loop root = 1..n for fork counts; add path counts via dub/2. Path-type triples use a unique path of $d$ vertices; fork-type triples have a unique branch point $r$ where the three directions lie in three different child subtrees. Each valid triple is counted exactly once.