倍增求 LCA
时间复杂度 ：
求出 表， 然后利用 表求出
vi d(N);
vii f(N, vi(20)); //f[x][i] 表示 x 向上跳 2 ^ i 步
//建立 ST 表
void dfs(int u, int father){
d[u] = d[father] + 1; //深度
f[u][0] = father;
rep(i, 1, 19)
f[u][i] = f[f[u][i - 1]][i - 1];
for(auto v : G[u]){
if(v == father) continue;
dfs(v, u);
}
return;
}
//求 u 和 v 的 lca
int lca(int u, int v){
if(d[u] < d[v]) swap(u, v); // u 作为深度更深的那一个
per(i, 19, 0)
if(d[f[u][i]] >= d[v])
u = f[u][i];
if(u == v) return v; //深度小的那个本省就是它们的 lca
per(i, 19, 0){
if(f[u][i] != f[v][i]){
u = f[u][i];
v = f[v][i];
}
}
return f[u][0];
}
例题：
下面的例题是一些题面中并没有明确告诉你去求 ，但是实际上运用到了 并且需要你自己去求的题目
天天爱跑步
题意
哪个天才可以来教我做这道题
思路
记 的深度为 , 的最近公共祖先为 , 出现观察员的时间为
到 的最短路一定是 从 先走到了 , 然后再从 走到 .
对于观察点 来说，有两种情况这个人贡献了价值， 分别为 走到 这段路上， 以及 走到 这段路上.
第一种情况：
是否经过角度的条件： 且
是否达到时间要求的条件 ：
引入一个 数组 , 表示深度等于 的数量的，使用 遍历
第二种情况：
是否经过角度的条件： 且
是否达到时间要求的角度 ：