Path Queries II - Complexity

Preprocessing takes $O(n)$ for DFS to compute sizes, depths, and parents. HLD decomposition takes $O(n)$. Building the segment tree takes $O(n)$. Total preprocessing: $O(n)$. Each path query walks $O(\log n)$ chains and queries $O(\log n)$ segment tree nodes per chain, giving $O(\log^2 n)$ per query.

Each update is $O(\log n)$. With $q$ queries, total time is $O(n + q \log^2 n)$, which handles $n, q = 200000$ easily within the $1$ second time limit.

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