Finding Triangular Stars

Fix a vertex $v$ as the center. Consider each direction incident to $v$, and define the length of that direction as the maximum distance one can go from $v$ through that direction.

A triangular star of size $K$ centered at $v$ exists if and only if there are at least three directions whose lengths are at least $K$. Therefore, the largest possible size of a triangular star centered at $v$ is the third largest value among the direction lengths of $v$.

We compute this value for every vertex. Root the tree arbitrarily and perform two tree DP passes.

Let $down_v$ be the maximum distance one can reach by going downward into the subtree of $v$. This can be computed in postorder.

Then let $up_v$ be the maximum distance one can reach from $v$ through the parent direction. When computing $up_u$ for a child $$ of , use the longest direction from excluding the direction toward .

For each vertex, collect the lengths $down_u+1$ for every child $u$, and also $up_v$ if is not the root. The third largest collected value is denoted by . Then vertex contributes one triangular star of each size .

Using a difference array, add $1$ to the range $[1,L_v]$ for every vertex $v$, and then take prefix sums to obtain all answers.

The time complexity is $O(N)$, and the memory complexity is $O(N)$.