长链剖分题表

长链剖分，类似于重链剖分(dsu on tree)的一种替代算法。最广泛的用法是优化与深度有关的树上DP，以及处理一些与点分治类似的问题。有一部分长链剖分题也可以用dsu on tree做，单复杂度往往会多一个log。

每个点找到高度最大的儿子作为自己的重儿子，连续的重儿子形成重链。可以发现，一个点到根要经过的重链最多为$O(sqrt{n})$个。一个点的任意祖先所在链长都不小于这个点所在的链长，容易证明，当重儿子信息$O(1)$传递，轻儿子信息$O(轻儿子所在重链长度)$传递时，均摊到每个点的复杂度都是$O(1)$，总复杂度为$O(n)$。

例一：[BZOJ3252]树上“k取方格数”问题，选k个叶子使到根路径并权值和最大。

这里只是用到了长链剖分的思想优化。

考虑网络流，发现树上不存在退流，于是模拟贪心，不断找叶子到根的权值最大的路径，计入答案后将路径清零。

显然每次可以取一条权值最大的长链即可。

 1 #include<queue>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<iostream>
 5 #include<algorithm>
 6 #define rep(i,l,r) for (int i=(l); i<=(r); i++)
 7 #define For(i,x) for (int i=h[x],k; i; i=nxt[i])
 8 typedef long long ll;
 9 using namespace std;
10 
11 const int N=200010;
12 ll ans,len[N];
13 int n,k,u,v,cnt,a[N],son[N],h[N],to[N],nxt[N];
14 priority_queue<ll>Q;
15 
16 void add(int u,int v){ to[++cnt]=v; nxt[cnt]=h[u]; h[u]=cnt; }
17 
18 void dfs(int x){
19     For(i,x){
20         dfs(k=to[i]);
21         if (len[k]>len[son[x]]) son[x]=k;
22     }
23     len[x]=len[son[x]]+a[x];
24 }
25 
26 void dfs2(int x,int top){
27     if (x==top) Q.push(len[x]);
28     if (son[x]) dfs2(son[x],top);
29     For(i,x) if ((k=to[i])!=son[x]) dfs2(k,k);
30 }
31 
32 int main(){
33     freopen("bzoj3252.in","r",stdin);
34     freopen("bzoj3252.out","w",stdout);
35     scanf("%d%d",&n,&k);
36     rep(i,1,n) scanf("%d",&a[i]);
37     rep(i,2,n) scanf("%d%d",&u,&v),add(u,v);
38     dfs(1); dfs2(1,1);
39     while (k && !Q.empty()) ans+=Q.top(),Q.pop(),k--;
40     printf("%lld
",ans);
41     return 0;
42 }

BZOJ3252

例二：[CF1009F]对每个子树找到一个深度使该子树内该深度的点最多。

f[x][i]表示x的i级子孙个数，发现重儿子的结果可以直接利用，轻儿子可以线性合并。

用指针实现二维数组以节省空间。这是此类问题的经典模板。

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<iostream>
 4 #include<algorithm>
 5 #define rep(i,l,r) for (int i=(l); i<=(r); i++)
 6 #define For(i,x) for (int i=h[x],k; i; i=nxt[i])
 7 typedef long long ll;
 8 using namespace std;
 9 
10 const int N=1000010;
11 int n,u,v,len[N],ans[N],fa[N],son[N],tmp[N],*f[N],*id=tmp;
12 int cnt,h[N],nxt[N<<1],to[N<<1];
13 void add(int u,int v){ to[++cnt]=v; nxt[cnt]=h[u]; h[u]=cnt; }
14 
15 void dfs(int x){
16     For(i,x) if ((k=to[i])!=fa[x]){
17         fa[k]=x; dfs(k);
18         if (len[k]>len[son[x]]) son[x]=k;
19     }
20     len[x]=len[son[x]]+1;
21 }
22 
23 void DP(int x){
24     f[x][0]=1;
25     if (son[x]) f[son[x]]=f[x]+1,DP(son[x]),ans[x]=ans[son[x]]+1;
26     For(i,x) if ((k=to[i])!=fa[x] && k!=son[x]){
27         f[k]=id; id+=len[k]; DP(k);
28         rep(j,1,len[k]){
29             f[x][j]+=f[k][j-1];
30             if (f[x][j]>f[x][ans[x]] || (f[x][j]==f[x][ans[x]] && j<ans[x])) ans[x]=j;
31         }
32     }
33     if (f[x][ans[x]]==1) ans[x]=0;
34 }
35 
36 int main(){
37     freopen("1009F.in","r",stdin);
38     freopen("1009F.out","w",stdout);
39     scanf("%d",&n);
40     rep(i,2,n) scanf("%d%d",&u,&v),add(u,v),add(v,u);
41     dfs(1); f[1]=id; id+=len[1]; DP(1);
42     rep(i,1,n) printf("%d
",ans[i]);
43     return 0;
44 }

CF1009F

例三：[COGS2652]树上每个点有两个权值ai,bi，找一条长为m的路径使sum(a[i])/sum(b[i])最小。

分数规划后变成找一条长度为m的最小路径，同样f[x][i]表示x开始往下的长为i的链的最小权值和为多少。

转移与更新答案显然，注意由于重儿子转移过来有一个全部加a[x]的操作，于是给每个点记录一个增量就好了。

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<iostream>
 4 #include<algorithm>
 5 #define rep(i,l,r) for (int i=(l); i<=(r); i++)
 6 #define For(i,x) for (int i=h[x],k; i; i=nxt[i])
 7 typedef long long ll;
 8 using namespace std;
 9 
10 const int N=200010;
11 int n,m,u,v,len[N],fa[N],son[N],a[N],b[N];
12 double val[N],tmp[N],*f[N],*id=tmp,ans=1e18;
13 int cnt,h[N],nxt[N<<1],to[N<<1];
14 void add(int u,int v){ to[++cnt]=v; nxt[cnt]=h[u]; h[u]=cnt; }
15 
16 void dfs(int x){
17     For(i,x) if ((k=to[i])!=fa[x]){
18         fa[k]=x; dfs(k);
19         if (len[k]>len[son[x]]) son[x]=k;
20     }
21     len[x]=len[son[x]]+1;
22 }
23 
24 void DP(int x,double mid){
25     val[x]=a[x]-mid*b[x]; f[x][0]=0;
26     if (son[x]) f[son[x]]=f[x]+1,DP(son[x],mid),val[x]+=val[son[x]],f[x][0]-=val[son[x]];
27     For(i,x) if ((k=to[i])!=fa[x] && k!=son[x]){
28         f[k]=id; id+=len[k]; DP(k,mid);
29         rep(j,0,min(len[k]-1,m-1))
30             if (m-j-1<len[x]) ans=min(ans,f[k][j]+val[k]+f[x][m-j-1]+val[x]);
31         rep(j,0,min(len[k]-1,m-1))
32             f[x][j+1]=min(f[x][j+1],f[k][j]+val[k]-val[x]+a[x]-mid*b[x]);
33     }
34     if (m<len[x]) ans=min(ans,f[x][m]+val[x]);
35 }
36 
37 int main(){
38     freopen("cogs2652.in","r",stdin);
39     freopen("cogs2652.out","w",stdout);
40     scanf("%d%d",&n,&m); m--;
41     rep(i,1,n) scanf("%d",&a[i]);
42     rep(i,1,n) scanf("%d",&b[i]);
43     rep(i,1,n) ans=min(ans,1.*a[i]/b[i]);
44     if (m==-2 || !m){ printf("%.2lf
",ans); return 0; }
45     rep(i,2,n) scanf("%d%d",&u,&v),add(u,v),add(v,u);
46     dfs(1); double l=0,r=N;
47     while (r-l>1e-3){
48         double mid=(l+r)/2;
49         memset(tmp,0x7f,sizeof(tmp)); ans=1e18;
50         id=tmp; f[1]=id; id+=len[1]; DP(1,mid);
51         if (ans>=0) l=mid; else r=mid;
52     }
53     if (l>=200000) puts("-1"); else printf("%.2lf
",l);
54     return 0;
55 }

COGS2652

例四：[BZOJ4543]一棵树中选3个点，两两距离相等，求方案数。

暴力DP方法加上长链剖分即可。

https://www.cnblogs.com/zhoushuyu/p/9468669.html

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<iostream>
 4 #include<algorithm>
 5 #define rep(i,l,r) for (int i=(l); i<=(r); i++)
 6 #define For(i,x) for (int i=h[x],k; i; i=nxt[i])
 7 typedef long long ll;
 8 using namespace std;
 9 
10 const int N=100010;
11 ll ans;
12 int n,u,v,len[N],fa[N],son[N],tmp[N<<2],*f[N],*g[N],*id=tmp;
13 int cnt,h[N],nxt[N<<1],to[N<<1];
14 void add(int u,int v){ to[++cnt]=v; nxt[cnt]=h[u]; h[u]=cnt; }
15 
16 void dfs(int x){
17     For(i,x) if ((k=to[i])!=fa[x]){
18         fa[k]=x; dfs(k);
19         if (len[k]>len[son[x]]) son[x]=k;
20     }
21     len[x]=len[son[x]]+1;
22 }
23 
24 void DP(int x){
25     if (son[x]) f[son[x]]=f[x]+1,g[son[x]]=g[x]-1,DP(son[x]);
26     f[x][0]=1; ans+=g[x][0];
27     For(i,x) if ((k=to[i])!=fa[x] && k!=son[x]){
28         f[k]=id; id+=len[k]<<1; g[k]=id; id+=len[k]<<1; DP(k);
29         rep(j,0,len[k]-1){
30             if (j) ans+=f[x][j-1]*g[k][j];
31             ans+=g[x][j+1]*f[k][j];
32         }
33         rep(j,0,len[k]-1){
34             g[x][j+1]+=f[x][j+1]*f[k][j];
35             if (j) g[x][j-1]+=g[k][j];
36             f[x][j+1]+=f[k][j];
37         }
38     }
39 }
40 
41 int main(){
42     freopen("bzoj4543.in","r",stdin);
43     freopen("bzoj4543.out","w",stdout);
44     scanf("%d",&n);
45     rep(i,2,n) scanf("%d%d",&u,&v),add(u,v),add(v,u);
46     dfs(1); f[1]=id; id+=len[1]<<1; g[1]=id; id+=len[1]<<1;
47     DP(1); printf("%lld
",ans);
48     return 0;
49 }

BZOJ4543

例五：[BZOJ3653]谈笑风生

同样没有什么要说的，暴力统计以深度为下标的信息，用上长链剖分复杂度就有保证了。

注意我们长链剖分的时候无法记录前缀和，但可以记录后缀和，且后缀和也是可以DP直接转移的。

 1 #include<cstdio>
 2 #include<vector>
 3 #include<cstring>
 4 #include<iostream>
 5 #include<algorithm>
 6 #define rep(i,l,r) for (int i=(l); i<=(r); i++)
 7 #define For(i,x) for (int i=h[x],k; i; i=nxt[i])
 8 typedef long long ll;
 9 using namespace std;
10 
11 const int N=300010;
12 int n,u,v,Q,dep[N],fa[N],son[N];
13 int cnt,len[N],sz[N],h[N],nxt[N<<1],to[N<<1];
14 ll ans[N],tmp[N],*f[N],*id=tmp;
15 struct P{ int x,y; };
16 vector<P>ve[N];
17 void add(int u,int v){ to[++cnt]=v; nxt[cnt]=h[u]; h[u]=cnt; }
18 
19 void dfs(int x){
20     dep[x]=dep[fa[x]]+1; sz[x]=1;
21     For(i,x) if ((k=to[i])!=fa[x]){
22         fa[k]=x; dfs(k); sz[x]+=sz[k];
23         if (len[k]>len[son[x]]) son[x]=k;
24     }
25     len[x]=len[son[x]]+1;
26 }
27 
28 void DP(int x){
29     if (son[x]) f[son[x]]=f[x]+1,DP(son[x]),f[x][0]+=f[son[x]][0];
30     f[x][0]+=sz[x]-1;
31     For(i,x) if ((k=to[i])!=fa[x] && k!=son[x]){
32         f[k]=id; id+=len[k]; DP(k);
33         rep(j,0,len[k]-1) f[x][j+1]+=f[k][j];
34         f[x][0]+=f[k][0];
35     }
36     int ed=ve[x].size()-1;
37     rep(i,0,ed){
38         int k=ve[x][i].y,id=ve[x][i].x;
39         ans[id]+=1ll*(sz[x]-1)*min(dep[x]-1,k);
40         if (k>=len[x]-1) ans[id]+=f[x][0]-sz[x]+1;
41             else ans[id]+=f[x][0]-sz[x]+1-f[x][k+1];
42     }
43 }
44 
45 int main(){
46     freopen("bzoj3653.in","r",stdin);
47     freopen("bzoj3653.out","w",stdout);
48     scanf("%d%d",&n,&Q);
49     rep(i,2,n) scanf("%d%d",&u,&v),add(u,v),add(v,u);
50     dfs(1);
51     rep(i,1,Q) scanf("%d%d",&u,&v),ve[u].push_back((P){i,v});
52     f[1]=id; id+=len[1]; DP(1);
53     rep(i,1,Q) printf("%lld
",ans[i]);
54     return 0;
55 }

BZOJ3653