@[王奕霏](/user/42479) 搜索子树，如果子树能访问到的最低时间戳高于父亲节点的时间戳，表明子树访问不了出父亲节点以外的点，说明父亲节点就是子树节点的最近公共祖先
by 楚风留罡 @ 2019-11-09 21:57:14
倍增最实用感觉
树剖太长了qwq(它真的太长了)
下面几种神仙解法不会
by Methylene_Blue @ 2019-11-09 21:58:46
@[FLK丿jn](/user/123993) 拓展欧拉序弄一下，就可以发现LCA是两个节点代表的区间中深度最小的
by LCuter @ 2019-11-09 21:59:12
Tarjan也好理解 ~~，只不过细节有点多~~
by Carlota @ 2019-11-09 21:59:49
@[Methylene_Blue](/user/58134) 树剖不长。。
~~~
const int N = 1e5 + 10 ;
struct node { int v , nxt ; } ;
node e[N << 1] ;
int head[N] , cnt = 0 ;
inline void Add(int u , int v) { e[++ cnt].v = v ; e[cnt].nxt = head[u] ; head[u] = cnt ; }
int size[N] , son[N] , d[N] ;
inline void Dfs1(int u) { size[u] = 1 ;
for(register int i = head[u] ; i ; i = e[i].nxt) {
int v = e[i].v ; if(v == fa[u]) continue ;
d[v] = d[u] + 1 , fa[v] = u , Dfs1(v) ; size[u] += size[v] ;
if(size[v] > size[son[u]]) son[u] = v ;
}
}
int top[N] , id[N] , tot = 0 ;
inline void Dfs2(int u , int tp) { top[u] = tp , id[u] = ++ tot ;
if(! son[u]) return ; Dfs2(son[u] , tp) ;
for(register int i = head[u] ; i ; i = e[i].nxt) { int v = e[i].v ;
if(v ^ fa[u] && v ^ son[u]) Dfs2(v , v) ;
}
}
inline int Lca(int x , int y) {
int fx = top[x] , fy = top[y] ;
while(fx ^ fy) { if(d[fx] < d[fy]) swap(x , y) , swap(fx , fy) ; fx = top[x = fa[fx]] ; }
if(d[x] > d[y]) swap(x , y) ;
return x ;
}
~~~
by 1saunoya @ 2019-11-09 22:03:49
@[Isaunoya](/user/96580) **Orz**
by Carlota @ 2019-11-09 22:05:40
询问多就用 欧拉序 + RMQ, 询问比较少就用树剖.
~~貌似LCT也可以来着~~
by Hydrate @ 2019-11-09 22:07:39
话说LCA好像是树剖的前置芝士。。。
by Carlota @ 2019-11-09 22:11:10
@[FLK丿jn](/user/123993) 严格来说并不算是 只是换根树剖可能用到倍增LCA
by 1saunoya @ 2019-11-09 22:17:57
@[北辰yama](/user/244079) @[Methylene_Blue](/user/58134) @[FLK丿jn](/user/123993) 我觉得倍增不好理解吧（而且板子也不好背）……相比下更喜欢打RMQ和树剖，这些纯数据结构的东西打熟了比倍增好用吧。
by QwQ237 @ 2019-11-09 22:30:24