1.重鏈剖分

做法：令x的兒子中子樹節(jié)點(diǎn)最多的兒子為重兒子，將一棵樹劃分成只由重兒子組成的一條條鏈

性質(zhì)：

1.每兩個(gè)點(diǎn)的最短路徑最多經(jīng)過logN條重鏈：每經(jīng)過一個(gè)節(jié)點(diǎn)，子樹大小至少減半，故在logN次一定走完

2.遍歷一棵樹，每次優(yōu)先遍歷重兒子，這棵樹的dfn序列中，保證每條重鏈一定連續(xù)，每棵樹及其子樹的節(jié)點(diǎn)一定連續(xù)

那么對(duì)于維護(hù)樹上信息的問題就可以把一棵樹轉(zhuǎn)化成一條鏈，然后維護(hù)鏈上的信息就好了

dfs1：先求出一棵樹每個(gè)節(jié)點(diǎn)的重兒子，每個(gè)節(jié)點(diǎn)的深度（求實(shí)際問題時(shí)一般要用到深度來確定鏈的編號(hào)），父親節(jié)點(diǎn)

void dfs1(int x,int f){sz[x]=1,hs[x]=0;fa[x]=f;for(int i=0;i<tu[x].size();i++){int p=tu[x][i];if(p==f) continue;dep[p]=dep[x]+1;dfs1(p,x);sz[x]+=sz[p];if(sz[p]>sz[hs[x]]) hs[x]=p;} }

dfs2：求出每個(gè)節(jié)點(diǎn)的dfs序（為轉(zhuǎn)化成序列問題做準(zhǔn)備），每條鏈的開頭

int times=0; void dfs2(int x,int up){top[x]=up,id[x]=++times;if(hs[x]!=0) dfs2(hs[x],up);for(int i=0;i<tu[x].size();i++){int p=tu[x][i];if(p==fa[x]||p==hs[x]) continue;dfs2(p,p);} }

剩下的具體問題具體分析，這里貼出來洛谷板子題的幾個(gè)操作（變量名很好看）

//ty是線段樹 void add_edge(int x,int y,int w){while(top[x]!=top[y]){ if(dep[top[x]]<dep[top[y]]) swap(x,y);//跳鏈頭較深的ty.add(1,1,a,id[top[x]],id[x],w);//記得是用idx=fa[top[x]];//到鏈頭已經(jīng)更新過了，就是這樣}if(dep[x]<dep[y]) swap(x,y);ty.add(1,1,a,id[y],id[x],w); } int query_edge(int x,int y){//同add_edgeint ans=0;while(top[x]!=top[y]){if(dep[top[x]]<dep[top[y]]) swap(x,y);ans=(ans+ty.query(1,1,a,id[top[x]],id[x]))%mod;x=fa[top[x]];}if(dep[x]<dep[y]) swap(x,y);ans=(ans+ty.query(1,1,a,id[y],id[x]))%mod;return ans; } void add_tree(int x,int w){//子樹編號(hào)連續(xù)ty.add(1,1,a,id[x],id[x]+sz[x]-1,w); } int query_tree(int x){return ty.query(1,1,a,id[x],id[x]+sz[x]-1); }

重鏈剖分邊權(quán)轉(zhuǎn)點(diǎn)權(quán)

將每條邊與兩端點(diǎn)較靠下的形成映射，然后還是維護(hù)節(jié)點(diǎn)信息就行了

2.長鏈剖分

1.做法：令兒子節(jié)點(diǎn)到葉子節(jié)點(diǎn)最遠(yuǎn)的點(diǎn)為此節(jié)點(diǎn)的長兒子，將一棵樹劃分成為由長兒子組成的一條條鏈

性質(zhì)：每個(gè)節(jié)點(diǎn)的k倍祖先所在的長鏈長度>=k（因?yàn)檫@個(gè)節(jié)點(diǎn)到其k倍祖先的距離為k）

利用這個(gè)性質(zhì)，就有了長鏈剖分應(yīng)用1：多次詢問一個(gè)節(jié)點(diǎn)的k倍祖先

思路：先利用倍增找到這個(gè)節(jié)點(diǎn)的2^n節(jié)點(diǎn)，使2^n<=k<=2^(n+1)

然后跳到這個(gè)點(diǎn)所在長鏈的鏈頭

對(duì)于每條長度為len的鏈，記錄其向上的len個(gè)節(jié)點(diǎn)和向下的len個(gè)節(jié)點(diǎn)

因?yàn)閘en>=k所以記錄這么多節(jié)點(diǎn)就行了

然后就直接查找

長鏈剖分：

void dfs1(long long x){for(long long i=1;(1<<i)<=a;i++) fa[x][i]=fa[fa[x][i-1]][i-1];for(long long i=0;i<tu[x].size();i++){long long p=tu[x][i];if(p==fa[x][0]) continue;d[p]=d[x]+1;fa[p][0]=x;dfs1(p);if(dep[ls[x]]<dep[p]) ls[x]=p;}dep[x]=dep[ls[x]]+1; } long long times=0; void dfs2(long long x,long long up){to_down[up].push_back(x);id[x]=++times,mp[times]=x,top[x]=up;if(ls[x]) dfs2(ls[x],up);for(long long i=0;i<tu[x].size();i++){long long p=tu[x][i];if(p==fa[x][0]||p==ls[x]) continue;dfs2(p,p);int nowp=p;for(long long j=0;j<dep[p];j++){if(!nowp) break;to_up[p].push_back(nowp);nowp=fa[nowp][0];}} }

查找：

long long get_ans(long long x,long long k){if(!k) return x;x=fa[x][Log[k]];k-=(1<<Log[k]);k-=(id[x]-id[top[x]]);x=top[x];if(k<=0) return to_down[x][-k];else return to_up[x][k]; }

2.長鏈剖分優(yōu)化dp

當(dāng)然優(yōu)化的是樹上dp了

思路：對(duì)于一條鏈的轉(zhuǎn)移一般好分析，那么令每一條長鏈上的信息一起保存，共用空間

剩下的就暴力好了

題目

暴力好想，dp[x][i]為x節(jié)點(diǎn)距離為i的子節(jié)點(diǎn)的個(gè)數(shù)

然后鏈上的信息每次傳遞下去就好了

#include<bits/stdc++.h> using namespace std; vector<int>tu[1001000]; int buf[2001000]; int a,dep[1001000],ls[1000100],ans[1000100]; int *dp[1001000],*now=buf; void dfs1(int x,int fa); void dfs2(int x,int fa); void write(int x); int main(){scanf("%d",&a);for(int i=1;i<a;i++){int o,k;scanf("%d%d",&o,&k);tu[o].push_back(k),tu[k].push_back(o);}dfs1(1,0);dp[1]=now,now+=dep[1];dfs2(1,0);for(int i=1;i<=a;i++) write(ans[i]),putchar('\n');return 0; } void dfs1(int x,int fa){for(int i=0;i<tu[x].size();i++){int p=tu[x][i];if(p==fa) continue;dfs1(p,x);if(dep[p]>dep[ls[x]]) ls[x]=p;}dep[x]=dep[ls[x]]+1; } void dfs2(int x,int fa){dp[x][0]=1;if(ls[x]){dp[ls[x]]=dp[x]+1;dfs2(ls[x],x);if(dp[x][ans[x]]<dp[x][ans[ls[x]]+1]) ans[x]=ans[ls[x]]+1;}for(int i=0;i<tu[x].size();i++){int p=tu[x][i];if(p==fa||p==ls[x]) continue;dp[p]=now,now+=dep[p];dfs2(p,x);for(int j=1;j<=dep[p];j++){dp[x][j]+=dp[p][j-1];if((dp[x][j]>dp[x][ans[x]])||(j<ans[x]&&dp[x][j]==dp[x][ans[x]])) ans[x]=j;}} } void write(int x){if(x>9) write(x/10);putchar(x%10+'0'); }

總結(jié)

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

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