$O(n \log^3 n)$。

整体二分每个询问的答案，问题转化为要在二分点判断是否长度达到 $k$ 连续一段属在同一棵子树。考虑每次二分从最低层依次加入结点并启发式合并，这样每次上升一层同一个子树内所有点打上同样的标记，转化为最长连续段单修区查。瓶颈在于 $O(n \log n)$ 次单修。

大样例 3 1.6s，大样例 4 压根跑不完，随机数据 $10^5$ 跑 8 s，因为树上启发式合并在随机数据上表现较差，而 CCF 不太可能去随机树结构，所以有希望多拿点分吗？