前言

一個長鏈剖分的小trick

問題

如題，數(shù)據(jù)范圍大概$10^5$

思路

我們知道重鏈剖分是什么，即選擇自己兒子中子樹節(jié)點樹最大的作為重兒子，其它兒子為輕兒子
而長鏈剖分則是選擇兒子中子樹深度最大的兒子為長兒子，其它為短兒子

這樣進行樹剖后就有一些很奇妙的性質(zhì)，即：一個節(jié)點的kth祖先所在的鏈的鏈長大于k
我們考慮：對于每一條長度為$x$的鏈，我們記錄鏈頭的每個kth祖先（$k\in [1,x]$），以及鏈中的一個元素
我們發(fā)現(xiàn)，這個的記錄時間復(fù)雜度和空間復(fù)雜度都是$\mathcal{O}(n)$的

那么，現(xiàn)在對于一個詢問，求點$u$的$k$th祖先，如果我們能夠$\mathcal{O}(1)$的找到其隨便的一個$k^{\prime }$th祖先（$k^{\prime }>?\frac{k}{2}?$），那我們就可以$\mathcal{O}(1)$的詢問$k$th祖先了（實際操作只需要在$k^{\prime }$祖先的數(shù)組里進行訪問即可）
考慮倍增，我們可以$\mathcal{O}(nlogn)$預(yù)處理，這樣我們就可以直接跳$2^i$th祖先了，在本題中，只要讓$i$滿足$2^i\le k,2^{i+1}>k$即可，這個東西我們也可以開個數(shù)組$\mathcal{O}(n)$預(yù)處理

綜上，這個做法就能做到$\mathcal{O}(nlogn)$預(yù)處理，$\mathcal{O}(1)$詢問了

代碼

咕咕咕咕咕
好像沒有模板題，所以就沒了
update by 2019/8/4
碰到了一道需要用這來優(yōu)化成$\mathcal{O}(n\sqrt{n})$的
luoguP3591 [POI2015]ODW

#include<cstdio> #include<cctype> #include<algorithm> #include<cmath> #include<vector> namespace fast_IO {const int IN_LEN=1000000,OUT_LEN=1000000;char ibuf[IN_LEN],obuf[OUT_LEN],*ih=ibuf+IN_LEN,*oh=obuf,*lastin=ibuf+IN_LEN,*lastout=obuf+OUT_LEN-1;inline char getchar_(){return (ih==lastin)&&(lastin=(ih=ibuf)+fread(ibuf,1,IN_LEN,stdin),ih==lastin)?EOF:*ih++;}inline void putchar_(const char x){if(oh==lastout)fwrite(obuf,1,oh-obuf,stdout),oh=obuf;*oh++=x;}inline void flush(){fwrite(obuf,1,oh-obuf,stdout);} } using namespace fast_IO; #define getchar() getchar_() #define putchar(x) putchar_((x)) //#include<ctime> #define rg register typedef long long ll; template <typename T> inline T max(const T a,const T b){return a>b?a:b;} template <typename T> inline T min(const T a,const T b){return a<b?a:b;} template <typename T> inline void mind(T&a,const T b){a=a<b?a:b;} template <typename T> inline void maxd(T&a,const T b){a=a>b?a:b;} template <typename T> inline T abs(const T a){return a>0?a:-a;} template <typename T> inline void Swap(T&a,T&b){T c=a;a=b;b=c;} //template <typename T> inline void swap(T*a,T*b){T c=a;a=b;b=c;} template <typename T> inline T gcd(const T a,const T b){if(!b)return a;return gcd(b,a%b);} template <typename T> inline T lcm(const T a,const T b){return a/gcd(a,b)*b;} template <typename T> inline T square(const T x){return x*x;}; template <typename T> inline void read(T&x) {char cu=getchar();x=0;bool fla=0;while(!isdigit(cu)){if(cu=='-')fla=1;cu=getchar();}while(isdigit(cu))x=x*10+cu-'0',cu=getchar();if(fla)x=-x; } template <typename T> inline void printe(const T x) {if(x>=10)printe(x/10);putchar(x%10+'0'); } template <typename T> inline void print(const T x) {if(x<0)putchar('-'),printe(-x);else printe(x); } const int maxn=50001,maxm=100001; std::vector<int>kth[maxn]; int head[maxn],nxt[maxm],tow[maxm],tmp; inline void addb(const int u,const int v) {tmp++;nxt[tmp]=head[u];head[u]=tmp;tow[tmp]=v; } int n,part,a[maxn],b[maxn],c[maxn],d[maxn]; int f[maxn][19],dep[maxn],son[maxn],nothead[maxn],F[maxn],top[maxn],las[maxn]; void dfs(const int u,const int fa) {dep[u]=1;for(rg int i=head[u];i;i=nxt[i]){const int v=tow[i];if(v==fa)continue;f[v][0]=F[v]=u;d[v]=d[u]+1,dfs(v,u);if(dep[v]+1>dep[u])dep[u]=dep[v]+1,son[u]=v;} } void dfs2(const int u,const int fa) {las[top[u]]=u;for(rg int i=head[u];i;i=nxt[i]){const int v=tow[i];if(v==fa)continue;if(v==son[u])top[v]=top[u],dfs2(v,u);else top[v]=v,dfs2(v,u);} } int LCA(int u,int v) {if(d[u]<d[v])Swap(u,v);int D=d[u]-d[v];for(rg int i=0;i<=16;i++)if(D&(1<<i))u=f[u][i];if(u==v)return u;for(rg int i=16;i>=0;i--)if(f[u][i]!=f[v][i])u=f[u][i],v=f[v][i];return F[u]; } int qz[maxn][231],id[maxn]; void DFS(const int u,const int fa) {for(rg int j=1,v=F[u];j<=part;j++)qz[u][j]=qz[v][j]+a[u],v=F[v];for(rg int i=head[u];i;i=nxt[i]){const int v=tow[i];if(v==fa)continue;DFS(v,u);} } int ks[65537]; int fe(int u,int dis) {if(dis==0)return u;u=f[u][ks[dis]];dis-=1<<ks[dis];if(u==0)return 0;return kth[top[u]][id[u]+dis]; } int main() {d[1]=1;for(rg int i=1;i<=16;i++)for(rg int j=1<<(i-1);j<(1<<i);j++)ks[j]=i-1;read(n),part=20;for(rg int i=1;i<=n;i++)read(a[i]);for(rg int i=1;i<n;i++){int u,v;read(u),read(v);addb(u,v),addb(v,u);}for(rg int i=1;i<=n;i++)read(b[i]);for(rg int i=1;i<n;i++)read(c[i]);dfs(1,0);top[1]=1,dfs2(1,0);for(rg int i=1;i<=16;i++)for(rg int j=1;j<=n;j++)f[j][i]=f[f[j][i-1]][i-1];for(rg int i=1;i<=n;i++)nothead[son[i]]=1;for(rg int i=1;i<=n;i++)if(!nothead[i]){std::vector<int>&t=kth[i];const int S=dep[i]<<1;t.resize(S+1);for(rg int j=1,u=las[i];u&&j<=S;j++){if(j<=dep[i])id[u]=j;t[j]=u,u=F[u];}}DFS(1,0);for(rg int i=1;i<n;i++){int u=b[i],v=b[i+1],step=c[i],lca=LCA(u,v);if(step<=part){int du=d[u]-d[lca],dv=d[v]-d[lca];int ans=0;int extra=du%step;du=du-extra+step;ans+=qz[u][step]-qz[fe(u,du)][step];dv+=extra;if(dv==0)print(ans);else{ans+=a[v];extra=(dv-1)%step+1;ans+=qz[fe(v,extra)][step]-qz[fe(v,dv)][step];print(ans);}}else{int ans=0;while(d[u]>=d[lca]){ans+=a[u];u=fe(u,step);}while(d[v]>d[lca]){ans+=a[v];v=fe(v,step);}print(ans);}putchar('\n');}return flush(),0; }

總結(jié)

挺巧妙的一個思路，在求kth祖先的次數(shù)比較多的時候可以使用

總結(jié)

以上是生活随笔為你收集整理的长链剖分：O(nlogn)预处理O(1)求kth祖先的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。