所謂長鏈剖分，就是對長鏈進行剖分

（逃）

前言

很優雅的算法
利用對指針進行魔法操作將 $n^2$ 的 dp 優化成線性
線性啊！！！

解析

CF1009F Dominant Indices

給定一棵以 $1$ 為根，$n$ 個節點的樹。設 $d(u,x)$ 為 $u$ 子樹中到 $u$ 距離為 $x$ 的節點數。
對于每個點，求一個最小的 $k$，使得 $d(u,k)$ 最大。

長剖板子題
設 $f_{x,d}$ 表示x子樹內到x距離為d的結點個數
則有：
$$f_{x,d}\leftarrow f_{son,d?1}$$
所以其實就是下標偏離了一位而已
那么如何解決呢？

長鏈剖分

定義一個子樹的深度是子樹內深度最大的兒子的深度
定義一個結點的重兒子是子樹深度最大的兒子
和重鏈剖分類似的，重兒子連成重鏈，單獨結點也算一個重鏈，每個結點都在唯一的重鏈上

void dfs1(int x,int fa){for(int i=fi[x];~i;i=p[i].nxt){int to=p[i].to;if(to==fa) continue;dfs1(to,x);if(1) son[x]=to;}len[x]=len[son[x]]+1; }

指針偏移

既然我們的父親dp值只是和兒子相比偏移了一位
那么我們就嘗試利用指針的便宜讓父親直接繼承兒子的dp
當然，繼承所有兒子的dp是無法實現的，那么我們就讓父親繼承重兒子的dp值，其他兒子暴力轉移

void dp(int x,int fa){f[x][0]=1;if(son[x]){f[son[x]]=f[x]+1;dp(son[x],x);ans[x]=ans[son[x]]+1;}for(int i=fi[x];~i;i=p[i].nxt){int to=p[i].to;if(to==fa||to==son[x]) continue;f[to]=now;now+=len[to];dp(to,x);for(int j=0;j<len[to];j++){f[x][j+1]+=f[to][j];if(f[x][j+1]>f[x][ans[x]]||(f[x][j+1]==f[x][ans[x]]&&j+1<ans[x])) ans[x]=j+1;}}if(f[x][ans[x]]==1) ans[x]=0; }

復雜度證明

每個重鏈從鏈頭向父親轉移，會產生重鏈長度的代價
由于重鏈長度和為結點個數，所以復雜度為 $O(n)$

注意！ 和重鏈剖分不同，每個結點到根節點的長鏈個數可以達到 $O(\sqrt{n})$ 級別

完整代碼

#include<bits/stdc++.h> using namespace std; #define ll long long #define ull unsigned long long #define debug(...) fprintf(stderr,__VA_ARGS__) const int N=1e6+100; const double eps=1e-12; inline ll read(){ll x(0),f(1);char c=getchar();while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}while(isdigit(c)) {x=(x<<1)+(x<<3)+c-'0';c=getchar();}return x*f; }int n; struct node{int to,nxt; }p[N<<1]; int fi[N],cnt; inline void addline(int x,int y){p[++cnt]=(node){y,fi[x]};fi[x]=cnt;return; } int son[N],len[N]; int buf[N],*f[N],*now=buf; void dfs(int x,int f){for(int i=fi[x];~i;i=p[i].nxt){int to=p[i].to;if(to==f) continue;dfs(to,x);if(len[to]>len[son[x]]) son[x]=to;}len[x]=len[son[x]]+1; } int ans[N]; void dp(int x,int fa){f[x][0]=1;if(son[x]){f[son[x]]=f[x]+1;dp(son[x],x);ans[x]=ans[son[x]]+1;}for(int i=fi[x];~i;i=p[i].nxt){int to=p[i].to;if(to==fa||to==son[x]) continue;f[to]=now;now+=len[to];dp(to,x);for(int j=0;j<len[to];j++){f[x][j+1]+=f[to][j];if(f[x][j+1]>f[x][ans[x]]||(f[x][j+1]==f[x][ans[x]]&&j+1<ans[x])) ans[x]=j+1;}}if(f[x][ans[x]]==1) ans[x]=0; } signed main(){ #ifndef ONLINE_JUDGE//freopen("a.in","r",stdin);//freopen("a.out","w",stdout); #endifmemset(fi,-1,sizeof(fi));cnt=-1;n=read();for(int i=1;i<n;i++){int x=read(),y=read();addline(x,y);addline(y,x);}dfs(1,0);f[1]=now;now+=len[1];dp(1,0);for(int i=1;i<=n;i++) printf("%d\n",ans[i]);return 0; } /**/

Thanks for reading!

總結

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

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