T2
倍增+换根即可，但赛时难写
赛时想得线段树二分，也可
回头一看老师代码，发现换根换的非常神奇，长见识了
方法0：
第一次思考，以为要记录走排名为 \(a_x\) 和 \(a_x+1\) 的两个倍增数组，但发现并不好合并，也许可以憋出来，但还是寄掉了
方法1：
xjk的思路是这样的：记 \(top_i\) 表示从 \(i\) 只向上跳最远距离，然后维护一个 \(sum_{i,j}\) 的倍增数组记录向上跳的和。而跳到顶部后还可能继续向下跳，遂记录 \(dwn_i\) 表示从 \(i\) 向下跳最远距离。我们也可以再开一个倍增数组记录向下跳的和，但这很麻烦，不如直接用总和 \(-\) 向上跳的和，复杂度 \(O(n \log n)\)
方法2：
老师的思路是这样的：对于 \(x\) 的儿子 \(y\) ，考虑当 \(y\) 子树内的询问跳到 \(x\) 时 \(x\) 的倍增数组会变成什么样。怎么修改？其实暴力重构即可
这么说比较难以理解，给一下代码：
void dfs2(int u){// 表示当前情况所有倍增数组都是以 u 为根的情况
for(auto i : ask[ u ]){
i.V -= b[ u ]; if(i.V < 0){ ans[ i.id ] = u; continue; }
ans[ i.id ] = e[ u ][ i.t - 1 ]; solve(ans[ i.id ], i.V);
}// 处理询问，因为当前以 u 为根， solve 里直接跳即可
for(auto v : e[ u ]){ if(v == fa[ u ]) continue; // 重点，换根
int nxt = e[ u ][ a[ u ] - 1 ]; if(v <= nxt) nxt = e[ u ][ a[ u ] ]; // 把 v 换成根时走哪个点
jp[ 0 ][ u ] = nxt;
For(i, 1, lg[ n ]){
jp[ i ][ u ] = jp[ i - 1 ][ jp[ i - 1 ][ u ] ];
sm[ i ][ u ] = sm[ i - 1 ][ u ] + sm[ i - 1 ][ jp[ i - 1 ][ u ] ];
} // 暴力重构
dfs2(v); // 递归计算
}
if(!a[ u ]) return ;
int nxt = e[ u ][ a[ u ] - 1 ]; if(fa[ u ] <= nxt) nxt = e[ u ][ a[ u ] ]; // 还原回去
jp[ 0 ][ u ] = nxt;
For(i, 1, lg[ n ]){
jp[ i ][ u ] = jp[ i - 1 ][ jp[ i - 1 ][ u ] ];
sm[ i ][ u ] = sm[ i - 1 ][ u ] + sm[ i - 1 ][ jp[ i - 1 ][ u ] ];
}
}
复杂度也是 \(O(n \log n)\)