CF1174F Ehab and the Big Finale
树链剖分。
先 s 1 求出 \(x\) 所在子树 \(y\)。
若 \(y\) 为 \(1\) 轻儿子，递归求解 \(y\)。
若 \(y\) 为重儿子，那么找到重链上与 \(x\) 深度相同的节点 \(c\).
调用 d c，此时 \(c\) 向上跳 \(x\) 与 \(c\) 距离的一半便是 \(lca\)，递归求解。
相当于走了 \(x\) 向上的所有轻，重链。
由于轻链，重链数量都是 \(\log n\) 级别，所以询问次数不会超过 \(36=2O(\log n)\).