再谈 qbxt2023国庆刷题 Day7 T2 树

T2

倍增+换根即可，但赛时难写

赛时想得线段树二分，也可

from:https://www.cnblogs.com/fox-konata/p/17742669.html

回头一看老师代码，发现换根换的非常神奇，长见识了

方法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)\)