長鏈剖分

• 長鏈剖分學習總結 | Bill Yang's Blog

簡介

對每個節點 \(p\), 定義 \(\operatorname{len} (p)\) 表示 \(p\) 到它子樹中葉子節點的最大長度.

類似重鏈剖分, 把每個節點 \(p\) 的兒子中 \(\operatorname{len}\) 最大的設為它的重兒子. 邊 \((p,son(p))\) 稱為重邊.

把重邊組成的極長子鏈稱為重鏈(或者長鏈).

長鏈剖分可以保證一個性質:

\[\begin{equation} \text{長鏈總長度} \le n \end{equation}\]

雖然很顯然, 但這個性質保證了一些利用長鏈剖分的算法的復雜度.

應用

求一個點的k級祖先

預處理 \(O(n \log n)\), 單次詢問 \(O(1)\).

其實并沒有什么卵用, 可以被倍增替代

優化一些關于長度的dp

先咕了...

例題: bzoj4543: [POI2014]Hotel加強版

可以得到一個關于鏈長度的dp方程, 因此利用長鏈剖分優化即可.

開空間時:

• 對于\(f\) 數組, 重鏈頂 \(p\) 和它的重鏈上的兒子只會用到 \(mem[f[p] ... f[p]+len[p]-1]\) 的空間;
• 對于\(g\) 數組, 重鏈頂 \(p\) 和它的重鏈上的兒子會用到 \(mem[g[p]-len[p]+1 ... g[p]+len[p]-1]\) 的空間.

因此開空間時需要開兩倍... 詳見代碼.

#include<cstdio> #include<iostream> #include<cmath> #include<cstring> #include<algorithm> #include<set> #include<map> using namespace std; #define rep(i,l,r) for(register int i=(l);i<=(r);++i) #define repdo(i,l,r) for(register int i=(l);i>=(r);--i) #define il inline typedef double db; typedef long long ll;//--------------------------------------- const int nsz=100050;int n; ll ans=0; struct te{int t,pr;}edge[nsz*2]; int hd[nsz],pe=1; void adde(int f,int t){edge[++pe]=(te){t,hd[f]};hd[f]=pe;} void adddb(int f,int t){adde(f,t);adde(t,f);} #define forg(p,i,v) for(int i=hd[p],v=edge[i].t;i;i=edge[i].pr,v=edge[i].t)int len[nsz]{-1},son[nsz]; ll mem[nsz*5],*f[nsz],*g[nsz],*pm=mem; void initp(int p,int l){ //開空間f[p]=pm,pm+=(l<<1)+2,g[p]=pm,pm+=l+2; }void dfs1(int p,int f){son[p]=0,len[p]=0;forg(p,i,v){if(v==f)continue;dfs1(v,p);if(len[v]>len[son[p]])son[p]=v,len[p]=len[v]+1;} }void dfs2(int p,int fa){if(son[p]){f[son[p]]=f[p]+1,g[son[p]]=g[p]-1;dfs2(son[p],p);}f[p][0]=1;ans+=g[p][0];forg(p,i,v){if(v==fa||v==son[p])continue;initp(v,len[v]);dfs2(v,p);rep(j,0,len[v]){if(j)ans+=f[p][j-1]*g[v][j];ans+=g[p][j+1]*f[v][j];}rep(j,0,len[v]){g[p][j+1]+=f[p][j+1]*f[v][j];if(j)g[p][j-1]+=g[v][j];f[p][j+1]+=f[v][j];}} }int main(){ios::sync_with_stdio(0),cin.tie(0);cin>>n;int a,b;rep(i,1,n-1)cin>>a>>b,adddb(a,b);dfs1(1,0);initp(1,len[1]);dfs2(1,0);cout<<ans<<'\n';return 0; }

轉載于:https://www.cnblogs.com/ubospica/p/10485904.html

總結

以上是生活随笔為你收集整理的[模板] 长链剖分的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。