求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种零食总数constintN1e510,M1050;constdoublePIacos(-1);constlonglongmod998244353,inf1e18;intfa[N][25],dep[N];intc[N][25];// 分每种零食来统计 看这种零食能不能在路上买到 而不是直接统计种数vectorintg[N];voiddfs(intnow,intf){forr(i,1,20)c[now][i]c[f][i];dep[now]dep[f]1;fa[now][0]f;for(inti1;(1i)dep[now];i){fa[now][i]fa[fa[now][i-1]][i-1];}for(autox:g[now]){if(xf)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])xfa[x][i];//从大到小遍历 利用二进制特性 分解dep[x]-dep[y]}if(xy)returnx;//xy同步上跳reforr(i,0,20){if(fa[x][i]!fa[y][i])xfa[x][i],yfa[y][i];//不是同一祖先就上跳 逐步逼近LCA//fa[x][i]fa[y][i]时不变 因为会有更近的相同祖先}returnfa[x][0];}voidsolve(){intn,q;cinnq;forr(i,1,n){intcx;cincx;c[i][cx]1;}forr(i,1,n-1){intu,v;cinuv;g[u].push_back(v);g[v].push_back(u);}dfs(1,0);// 以1为根forr(i,1,q){intans0;ints,t;cinst;intflca(s,t);forr(k,1,20){// 统计每种零食是否存在intcntc[s][k]c[t][k]-c[f][k]-c[fa[f][0]][k];ans(cnt0);}coutansendl;}}