LCA(倍增)

1. inline void dfs(int u, int f)
2. {
3.         fa[u][0] = f;
4.         dep[u] = dep[f] + 1;
5.         for(int i = 1; i <= 26; ++i)
6.             fa[u][i] = fa[fa[u][i - 1]][i - 1];
7.         int v;
8.         for(int e = hd[u]; e; e = nt[e])
9.             if((v = to[e]) ^ f)
10.                 dfs(v, u);
11. }
12. inline int LCA(int u, int v)
13. {
14.         if(dep[u] < dep[v]) swap(u, v);
15.         if(u == v) return u;
16.         for(int i = 26; i >= 0; --i)
17.             if(dep[fa[u][i]] >= dep[v])
18.                 u = fa[u][i];
19.         if(u == v) return u;
20.         for(int i = 26; i >= 0; --i)
21.             if(fa[u][i] ^ fa[v][i])
22.                 u = fa[u][i], v = fa[v][i];
23.         return fa[u][0];
24. }

复制代码

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！