Complexity Analysis

Preprocessing takes $O(n)$ to compute sizes and depths, $O(n)$ to decompose into chains, and $O(n)$ to build the segment tree. Total preprocessing: $O(n)$. Each query walks $O(\log n)$ chains and does $O(\log n)$ work per chain via segment tree queries.

Total per query: $O(\log^2 n)$. With $q$ queries, total time is $O(n + q \log^2 n)$. Space is $O(n)$ for arrays and the segment tree. This handles $n, q = 200000$ easily within time limits.

Space complexity is $O(n)$ for the data structures used.