Tree, TREE!!!

Let’s count pairs, not roots.

For every root $r$, $|S_r|$ is the number of vertices $v$ that can appear as the LCA of some $k$ chosen vertices. So the answer is

$$\sum_{r=1}^n |S_r| = \#\{(r,v): v \text{ can be an LCA when the root is } r\}.$$

That ordered-pair view is the whole problem. The tree tries to look scary by yelling TREE in all caps, but it’s mostly just component sizes.

When can a vertex be the LCA?

Fix a root $r$ and a candidate LCA vertex $v$.

In the tree rooted at $r$, for $v$ to be the LCA of some $k$ nodes, all chosen nodes must be inside the subtree of $v$.

Now here is the key simple point: if the subtree of $v$ has at least $k$ vertices, then $v$ is always achievable.

Why? Pick $v$ itself as one of the chosen vertices, then pick any other $k-1$ vertices from its subtree. Since one chosen node is $v$, the LCA is immediately $v$.

So we do not need some annoying “chosen nodes must come from two child subtrees” casework. That would only matter if we were forbidden from choosing $v$ itself, and we are not. Classic false assumption trap.

Therefore:

$$v \in S_r \iff \text{subtree size of } v \text{ when rooted at } r \ge k.$$

Translate subtree size using components

Delete vertex $v$ from the tree. This creates one component for each neighbor of $v$.

If $r = v$, then the subtree of $v$ is the whole tree, so its size is $n$, which is always at least $k$. Thus every vertex $v$ contributes once for root $r=v$.

If $r \ne v$, then $r$ lies in exactly one component after deleting $v$. Call its size $c$.

When the tree is rooted at $r$, that component is the parent side of $v$, so it is outside the subtree of $v$. Everything else, plus $v$, is inside the subtree.

So:

$$\text{subtree size of } v = n - c.$$

We need:

$$n - c \ge k.$$

Equivalent:

$$c \le n-k.$$

So for a fixed vertex $v$, each surrounding component of size $c$ contributes exactly $c$ valid roots if $c \le n-k$, because every root inside that component gives the same parent side.

Also add $1$ for $r=v$.

Thus contribution of vertex $v$ is:

$$1 + \sum_{\text{components } C \text{ of } T-v} [|C| \le n-k] \cdot |C|.$$

The final answer is the sum of that over all $v$.

Computing the component sizes

Root the tree anywhere, say at $1$, just for DFS bookkeeping.

Let $sub[u]$ be the subtree size of $u$ in this arbitrary rooting.

For a vertex $v$:

• For every child $to$ of $v$ in the DFS tree, the component through $to$ after deleting $v$ has size $sub[to]$.
• If $v$ has a parent, the component through the parent has size $n - sub[v]$.

These are exactly all component sizes around $v$.

So we can do one iterative DFS to compute parents and subtree sizes, then loop over every edge direction/component once.

Initialize:

$$ans = n$$

because every $v$ contributes for root $r=v$.

Then for every component size $c$ around every vertex, add $c$ if:

$$c \le n-k.$$

That’s it. No reroot DP circus needed.

Complexity

Each edge gives two neighbor-side component sizes total, one from each endpoint’s perspective. So everything is linear:

$$O(n)$$

per test case, and $O(\sum n)$ overall. Memory is also $O(n)$.

The answer can be as large as $n^2$, so use long long.