求LCA 倍增法

倍增法

在线算法，单独处理每个查询

DFS()——祖先递推O ( n l o g 2 n ) O(nlog_2n)O(nlog2​n)

f a [ x ] [ i ] fa[x][i]fa[x][i]表示从x xx向上跳2 i 2^i2i步能到达的祖先
f a [ x ] [ i ] = f a [ f a [ x ] [ i − 1 ] ] [ i − 1 ] fa[x][i]=fa[fa[x][i-1]][i-1]fa[x][i]=fa[fa[x][i−1]][i−1]
右端：f a [ x ] [ i − 1 ] fa[x][i-1]fa[x][i−1]=从x xx向上跳2 i − 1 2^{i-1}2i−1步到达的点，从这个点再跳2 i − 1 2^{i-1}2i−1能到达f a [ x ] [ i ] fa[x][i]fa[x][i]
利用二进制特征能跳到任意步的祖先

LCA()——同步上跳O ( m l o g 2 n ) O(mlog_2n)O(mlog2​n)

基本思路

• 把x\y提到相同深度
• 让x\y同步向上走，每走一步判断是否相遇

例1：零食采购

摘自题解：
列表项第i种零食是否包含 = 起始节点买到第i种零食总数 + 终点买到第i种零食总数 - 公共祖先买到第i种零食总数 - 公共祖先上一个节点买到第i种零食总数

constintN=1e5+10,M=1050;constdoublePI=acos(-1);constlonglongmod=998244353,inf=1e18;intfa[N][25],dep[N];intc[N][25];// 分每种零食来统计 看这种零食能不能在路上买到 而不是直接统计种数vector<int>g[N];voiddfs(intnow,intf){forr(i,1,20)c[now][i]+=c[f][i];dep[now]=dep[f]+1;fa[now][0]=f;for(inti=1;(1<<i)<=dep[now];i++){fa[now][i]=fa[fa[now][i-1]][i-1];}for(autox:g[now]){if(x==f)continue;dfs(x,now);}}intlca(intx,inty){if(dep[x]<dep[y])swap(x,y);//x深 y浅//xy提到相同深度reforr(i,0,20){if(dep[fa[x][i]]>=dep[y])x=fa[x][i];//从大到小遍历 利用二进制特性 分解dep[x]-dep[y]}if(x==y)returnx;//xy同步上跳reforr(i,0,20){if(fa[x][i]!=fa[y][i])x=fa[x][i],y=fa[y][i];//不是同一祖先就上跳 逐步逼近LCA//fa[x][i]=fa[y][i]时不变 因为会有更近的相同祖先}returnfa[x][0];}voidsolve(){intn,q;cin>>n>>q;forr(i,1,n){intcx;cin>>cx;c[i][cx]=1;}forr(i,1,n-1){intu,v;cin>>u>>v;g[u].push_back(v);g[v].push_back(u);}dfs(1,0);// 以1为根forr(i,1,q){intans=0;ints,t;cin>>s>>t;intf=lca(s,t);forr(k,1,20){// 统计每种零食是否存在intcnt=c[s][k]+c[t][k]-c[f][k]-c[fa[f][0]][k];ans+=(cnt>0);}cout<<ans<<endl;}}