長鏈剖分題集及總結(jié)

樹剖中我們常用的是重鏈剖分，是用于解決樹上兩點路徑上相關(guān)問題的利器，當(dāng)然也可以用于解決一些子樹問題。今天和大家聊的是另一種樹剖，基于深度的剖分

具體怎么剖就不講了，下面稍微講一下他的性質(zhì)和應(yīng)用

一.鏈長和是O(n)

二.任意一個點k次祖先y所在的長鏈長度$\ge$k

三.從任意一個點向上跳長鏈$\le \sqrt{n}$次

應(yīng)用

1.$O(nlogn)?O(1)求k次祖先$

本質(zhì)上是利用性質(zhì)二，維護(hù)每個長鏈頂端向下和向上長鏈長度的點，這樣通過倍增跳過去，然后$O(1)$查詢，比一般倍增的$O(nlogn)—O(1)$更優(yōu)

這里直接掛代碼了 洛谷P5903

//樹上k級祖先 O(nlogn)~O(1) #include<bits/stdc++.h> #define pb push_back using namespace std; typedef long long ll; const int maxn=5e5+5; #define ui unsigned int ui S; inline ui get() {S ^= S << 13;S ^= S >> 17;S ^= S << 5;return S; } int f[maxn][20],n,u,v,len[maxn],head[maxn],next1[maxn<<1],ver[maxn<<1],tot,hbit[maxn],m,lg[maxn]; vector<int>U[maxn],D[maxn]; void add(int x,int y){ver[++tot]=y,next1[tot]=head[x],head[x]=tot; }struct LCD{int fa[maxn],dep[maxn],md[maxn],hson[maxn],top[maxn];//md[x]表示該點子樹的最深深度void dfs1(int x,int fat){f[x][0]=fa[x]=fat;md[x]=dep[x]=dep[fat]+1;for(int i=1;i<=lg[dep[x]];++i)f[x][i]=f[f[x][i-1]][i-1];for(int i=head[x];i;i=next1[i]){int y=ver[i];if(y==fat)continue;dfs1(y,x);if(md[y]>md[hson[x]])hson[x]=y,md[x]=md[y];}}void dfs2(int x,int t){top[x]=t;len[x]=md[x]-dep[top[x]];//鏈長if(!hson[x])return;dfs2(hson[x],t);for(int i=head[x];i;i=next1[i]){int y=ver[i];if(y==fa[x]||y==hson[x])continue;dfs2(y,y);}}void init(int x){dfs1(x,0);dfs2(x,x);}int query(int x,int k){//x的k級祖先if(k>dep[x])return 0;if(!k)return x;x=f[x][hbit[k]];k^=(1<<hbit[k]);if(dep[x]-dep[top[x]]==k)return top[x];if(dep[x]-dep[top[x]]>k)return D[top[x]][dep[x]-dep[top[x]]-k-1];return U[top[x]][k-(dep[x]-dep[top[x]])-1];} }lcd; int main(){cin>>n>>m>>S;int rt=0;for(int i=1;i<=n;++i){scanf("%d",&u);if(!u)rt=i;else{add(i,u);add(u,i);}}for(int i=1;i<=n;++i)lg[i]=lg[i-1]+(1<<lg[i-1]==i);lcd.init(rt);for(int i=1;i<=n;++i){if(i==lcd.top[i]){int l=0,x=i;while(l<len[i]&&x)x=f[x][0],++l,U[i].pb(x);l=0,x=i;while(l<len[i])x=lcd.hson[x],++l,D[i].pb(x);}}int mx=1;for(int i=1;i<=n;++i){if((i>>mx)&1)++mx;hbit[i]=mx-1;}ll ans=0;int preans=0;for(int i=1;i<=m;++i){u=(get()^preans)%n+1,v=(get()^preans)%lcd.dep[u];preans=lcd.query(u,v);ans^=1ll*i*preans;}cout<<ans;return 0; }

二、快速維護(hù)可合并的與深度有關(guān)的子樹信息

一般都是長鏈剖分優(yōu)化dp

常見的有兩種，一種是長鏈剖分dp后綴和維護(hù)，一種是直接優(yōu)化dp，先講第一種

長鏈剖分+后綴和 常用于解決離某子樹的距離有限制比如$<=k或者>k$的點滿足xx條件的有多少

1.洛谷P3899

題意：

統(tǒng)計有序三元組(a,b,c)滿足a,b都是c的祖先，且a,b在樹上的距離<=k

思路：

這題在線有可持久化線段樹、線段樹合并，離線有長鏈剖分、樹狀數(shù)組。其他幾種寫法我或許會在未來鴿掉的可持久化線段樹上補(bǔ)充

其實本質(zhì)上一看就是個二維偏序啦，就可以亂搞了，但是我們想用長鏈剖分做，首先$b$在$a$上面的很傻逼，就$(sz[a]?1)?min(dep[a]?1,k)$

關(guān)鍵是下面

對于a下面的每個點其實就是對于所有的<=k統(tǒng)計其$\sum (sz[x]?1)$而已，<=k一般直接轉(zhuǎn)為后綴和

直接$dp[i][j]$表示以$i$為根節(jié)點，距離$i$$>=j$下,$ab$為$c$祖先，$bc$在$a$子樹下的數(shù)量

$dp[x][0]$就是整顆子樹，注意這里一般都用指針轉(zhuǎn)移，長鏈直接$O(1)$,短鏈就直接枚舉，由勢能分析容易證得其實是$O（n?md[1]）$的，空間也是$O(n)$，轉(zhuǎn)移$dp[x][i+1]+=dp[y][i]$,但由于使用指針，所以長兒子不用轉(zhuǎn)移，直接賦值的時候$O(1)$轉(zhuǎn)移了，但是需要注意的是，此時$dp[x][0]$并沒有更新,還是得+=，統(tǒng)計答案的時候減法獲取需要答案即可，個人認(rèn)為這道非常適合當(dāng)長鏈剖分優(yōu)化dp后綴和的模板

#include<bits/stdc++.h> #define pb push_back #define fi first #define se second using namespace std; typedef long long ll; const int maxn=3e5+5; ll *dp[maxn],tmp[maxn],*id=tmp,ans[maxn]; int sz[maxn],head[maxn],ver[maxn<<1],next1[maxn<<1],n,q,hson[maxn],md[maxn],dep[maxn],tot; typedef pair<int,int>P;//dp[i][j]以i為根子樹距離i>=j下,ab為c祖先，bc在a子樹下的數(shù)量 vector<P>Q[maxn]; void dfs1(int x,int f){ dep[x]=dep[f]+1;sz[x]=1;for(int i=head[x];i;i=next1[i]){int y=ver[i];if(y==f)continue;dfs1(y,x);sz[x]+=sz[y];if(md[y]>md[hson[x]])hson[x]=y;}md[x]=md[hson[x]]+1; } void add(int x,int y){ver[++tot]=y,next1[tot]=head[x],head[x]=tot; } void dfs(int x,int f){dp[x][0]=sz[x]-1;if(hson[x]){//指針，長鏈直接賦值不用+=dp[hson[x]]=dp[x]+1;dfs(hson[x],x);dp[x][0]+=dp[hson[x]][0];//但>=0沒統(tǒng)計}for(int i=head[x];i;i=next1[i]){int y=ver[i];if(y==f||y==hson[x])continue;dp[y]=id;id+=md[y];dfs(y,x);dp[x][0]+=dp[y][0];for(int j=0;j<md[y];++j)//后綴和維護(hù)dp[x][j+1]+=dp[y][j];}for(auto&v:Q[x]){ans[v.fi]+=1ll*(sz[x]-1)*min(dep[x]-1,v.se);if(v.se<md[x]-1)ans[v.fi]+=dp[x][0]-dp[x][v.se+1]-(sz[x]-1);else ans[v.fi]+=dp[x][0]-(sz[x]-1);} } int main(){scanf("%d%d",&n,&q);int u,v;for(int i=1;i<n;++i){scanf("%d%d",&u,&v);add(u,v);add(v,u);}dfs1(1,0);dp[1]=id;id+=md[1];for(int i=1;i<=q;++i){scanf("%d%d",&u,&v);Q[u].pb({i,v});}dfs(1,0);for(int i=1;i<=q;++i)cout<<ans[i]<<"\n";return 0; }

2.[計蒜客 42385]

icpc徐州防AK題，但感覺學(xué)會長鏈剖分后很套路

[外鏈圖片轉(zhuǎn)存失敗,源站可能有防盜鏈機(jī)制,建議將圖片保存下來直接上傳(img-sRu9bZS0-1615813234887)(C:\Users\98753\AppData\Roaming\Typora\typora-user-images\image-20210315170001435.png)]

其實就是計算每個點為根上面那個東西，距離<=k,

枚舉已經(jīng)$O(lo{g}^{2}n)$了，所以我們使用長鏈剖分維護(hù)，暴力枚舉兩位后，表示出某兩點對于這兩位的4種狀態(tài)，同樣轉(zhuǎn)移即可，這里下面用了另外一種方法，就是用dfs序列表示點的位置，然后全部轉(zhuǎn)移到長兒子上，其實原理一樣，更推薦寫指針式的

#include<bits/stdc++.h> using namespace std; const int maxn=1e5+5; typedef unsigned long long ull; int head[maxn],ver[maxn<<1],next1[maxn<<1],tot,n,K,a[maxn],cnt[maxn][4],dfn[maxn],st[maxn],ti,k1,k2; ull ans[maxn]; void add(int x,int y){ver[++tot]=y,next1[tot]=head[x],head[x]=tot; } struct LCD{int md[maxn],hson[maxn];void dfs1(int x,int f){for(int i=head[x];i;i=next1[i]){int y=ver[i];if(y==f)continue;dfs1(y,x);if(md[y]>md[hson[x]])hson[x]=y;}md[x]=md[hson[x]]+1;} }lcd; ull getS(int x,int k,int sta){if(k<lcd.md[x]-1)return cnt[dfn[x]][sta]-cnt[dfn[x]+k+1][sta];return cnt[dfn[x]][sta]; } void dfs(int x,int f){//cnt[i]表示以i為根數(shù)字某兩位狀態(tài)的數(shù)量dfn[x]=++ti;cnt[dfn[x]][st[x]]++;if(lcd.hson[x]){dfs(lcd.hson[x],x);for(int i=0;i<4;++i)cnt[dfn[x]][i]+=cnt[dfn[lcd.hson[x]]][i];}for(int i=head[x];i;i=next1[i]){int y=ver[i];if(y==f||y==lcd.hson[x])continue;dfs(y,x);for(int j=0;j<4;++j)cnt[dfn[x]][j]+=cnt[dfn[y]][j];//短兒子更新dpfor(int j=0;j<lcd.md[y];++j)for(int k=0;k<4;++k)//全部轉(zhuǎn)移給長兒子鏈上,維護(hù)后綴和cnt[dfn[x]+j+1][k]+=cnt[dfn[y]+j][k];//長兒子鏈上cnt[i]維護(hù)dep>=i且x子樹內(nèi)的結(jié)點的和}for(int i=0;i<2;++i)ans[x]+=getS(x,K,i)*getS(x,K,3^i)<<(k1+k2); } int main(){scanf("%d%d",&n,&K);for(int i=1;i<=n;++i)scanf("%d",&a[i]);int x;for(int i=2;i<=n;++i){scanf("%d",&x);add(i,x);add(x,i);}lcd.dfs1(1,0);for(k1=0;k1<=29;++k1){for(k2=k1+1;k2<=29;++k2){for(int k=1;k<=n;++k){st[k]=0;if(a[k]&(1<<k1))st[k]|=1;if(a[k]&(1<<k2))st[k]|=2;for(int i=0;i<4;++i)cnt[k][i]=0;}ti=0;dfs(1,0);}}for(int i=1;i<=n;++i)ans[i]<<=1;for(k1=k2=0;k1<=29;k1++,k2++){for(int k=1;k<=n;++k){if(a[k]&(1<<k1))st[k]=3;else st[k]=0;for(int i=0;i<4;++i)cnt[k][i]=0;}ti=0;dfs(1,0);}for(int i=1;i<=n;++i)cout<<ans[i]<<'\n';return 0; }

長鏈剖分直接優(yōu)化DP,其實思路一樣，都是利用長鏈的特性減少時間復(fù)雜度

先看下這題

1.bzoj4543

這是一道非常狀態(tài)非常變態(tài)的樹形DP+長鏈剖分優(yōu)化題，所以重寫了一篇，詳情請看這里

https://blog.csdn.net/weixin_45539557/article/details/114848353?spm=1001.2014.3001.5501

2.cf1009E

題意：給一顆樹，$f[i][j]$表示$i$的子樹中距離$i$距離為$j$的點數(shù)，對每個$i$求出最大的$j$

思路：

首先是裸的長剖沒意見吧。轉(zhuǎn)移和上一題完全一樣，在轉(zhuǎn)移的時候順便記錄一下答案就好了，需要注意的是，我是每次用當(dāng)前重兒子+1的答案，所以最后如果方案數(shù)最少是一種，也就是本身的話，答案得更新為0這個位置

#include<bits/stdc++.h>using namespace std; const int maxn=1e6+5; typedef long long ll; ll *f[maxn],tmp[maxn],*id=tmp,g[maxn],head[maxn],ver[maxn<<1],next1[maxn<<1]; int md[maxn],hson[maxn],tot,ans[maxn],a,b,n; void add(int x,int y){ver[++tot]=y,next1[tot]=head[x],head[x]=tot; } void dfs1(int x,int f){for(int i=head[x];i;i=next1[i]){int y=ver[i];if(y==f)continue;dfs1(y,x);if(md[y]>md[hson[x]])hson[x]=y;}md[x]=md[hson[x]]+1; } void dfs(int x,int fa){if(hson[x]){f[hson[x]]=f[x]+1;dfs(hson[x],x);ans[x]=ans[hson[x]]+1;}f[x][0]=1;for(int i=head[x];i;i=next1[i]){int y=ver[i];if(y==fa||y==hson[x])continue;f[y]=id;id+=md[y];dfs(y,x);for(int j=1;j<=md[y];++j){f[x][j]+=f[y][j-1];if(f[x][j]>f[x][ans[x]]||(f[x][j]==f[x][ans[x]]&&ans[x]>j))ans[x]=j;}}if(f[x][ans[x]]==1)ans[x]=0;//特判最大值為1的時候 因為前面ans賦值最多為0 } int main(){scanf("%d",&n);for(int i=1;i<n;++i){scanf("%d%d",&a,&b);add(a,b);add(b,a);}dfs1(1,0);f[1]=id;id+=md[1];dfs(1,0);for(int i=1;i<=n;++i)cout<<ans[i]<<"\n";return 0; }

3.計蒜客40257 2019 icpc南昌E題

也是道變態(tài)題，另寫了一篇

https://blog.csdn.net/weixin_45539557/article/details/114850692

總結(jié)：很明顯，長鏈剖分在對于深度相關(guān)的信息合并的時候具有很優(yōu)的復(fù)雜度，常見的前綴轉(zhuǎn)后綴和，dp優(yōu)化用指針實現(xiàn)，也是比較套路的事情

總結(jié)

以上是生活随笔為你收集整理的长链剖分题集及总结的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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