ToB企服应用市场:ToB评测及商务社交产业平台
标题:
LCA(倍增)
[打印本页]
作者:
麻花痒
时间:
2022-8-10 10:02
标题:
LCA(倍增)
inline void dfs(int u, int f)
{
fa[u][0] = f;
dep[u] = dep[f] + 1;
for(int i = 1; i <= 26; ++i)
fa[u][i] = fa[fa[u][i - 1]][i - 1];
int v;
for(int e = hd[u]; e; e = nt[e])
if((v = to[e]) ^ f)
dfs(v, u);
}
inline int LCA(int u, int v)
{
if(dep[u] < dep[v]) swap(u, v);
if(u == v) return u;
for(int i = 26; i >= 0; --i)
if(dep[fa[u][i]] >= dep[v])
u = fa[u][i];
if(u == v) return u;
for(int i = 26; i >= 0; --i)
if(fa[u][i] ^ fa[v][i])
u = fa[u][i], v = fa[v][i];
return fa[u][0];
}
复制代码
免责声明:如果侵犯了您的权益,请联系站长,我们会及时删除侵权内容,谢谢合作!
欢迎光临 ToB企服应用市场:ToB评测及商务社交产业平台 (https://dis.qidao123.com/)
Powered by Discuz! X3.4