P8025 【树链剖分求祖先】

P8025 【树链剖分求祖先】

这题的题意简单，简单分类讨论一下这里就不赘述了。最后题目就简化成求一个点的 \(k\) 级祖先。

开始会的解法是倍增，但是常数过高被卡了。

常数更优秀的做法是树剖，每一次跳树链，最后可能有一条链太长只能跳一部分，这是因为树链剖分的 \(dfn\) 序是有序的，即每条链占的是一段区间，所以直接查询 \(dfn\) 数组即可。

int jump(int u, int t) { //从 u 点往上跳 t 次
	while(t > 0) {
		if(t - (dep[u] - dep[top[u]] + 1) >= 0) t -= dep[u] - dep[top[u]] + 1, u = fa[top[u]];
		else break;
	}
	return wt[id[u] - t];
}