【算法簡介】

長鏈剖分的思想很簡單，和樹剖基本一致，就是把維護的子樹節點最多改成了子樹深度最大

這種數據結構一般用于優化動態規劃（一般涉及了長度的dp）

【習題】

1.P3899 [湖南集訓]談笑風生

【題意】

求樹上的三個點構成的點對(a,b,c)，給定a求滿足a和b是c的祖先，a和b的距離不超過給定的k

【分析】

分類討論

1.當b比a高時，c點的可能取值有siz[a]-1個，b的取值有min(dep[b],dep[a],k)種，相乘即可

2.當b比a低時，c點的可能取值有siz[b]-1個，b的取值為min(dep[葉子]-dep[a],k)，也是相乘

第一部分的貢獻很好計算

計算第二部分貢獻，發現每個節點的貢獻可以賦給長兒子很多，所以用到了長鏈剖分來優化

維護一個后綴和，計算每個點的后綴和貢獻

從鏈的最深點開始的點，第二部分貢獻加上差分的和即可

注意實現過程中，因為要從父親節點繼承信息，所以開的數組要用指針版，方便賦值

【代碼】

#include<bits/stdc++.h> using namespace std; const int maxn=3e5+5; typedef long long ll; int head[maxn],n,m,tot; ll siz[maxn],ans[maxn],tmp[maxn],*s[maxn],*temp=tmp; struct edge {int to,nxt; }e[maxn<<1]; void add(int x,int y) {e[++tot].to=y; e[tot].nxt=head[x]; head[x]=tot; } struct query {int no,z; }; vector <query> q[maxn]; int dep[maxn],son[maxn],md[maxn]; void dfs1(int x,int fa) {dep[x]=md[x]=dep[fa]+1; siz[x]=1;for(int i=head[x];i;i=e[i].nxt){int to=e[i].to;if(to==fa) continue;dfs1(to,x);siz[x]+=siz[to];if(md[to]>md[son[x]]) son[x]=to;}if(son[x]) md[x]=md[son[x]]; } void dfs(int x,int fa) {s[x][0]=siz[x]-1;if(son[x]) s[son[x]]=s[x]+1,dfs(son[x],x),s[x][0]+=s[son[x]][0];for(int i=head[x];i;i=e[i].nxt){int to=e[i].to;if(to==fa || to==son[x]) continue;s[to]=temp; temp+=md[to]-dep[to]+1;dfs(to,x);for(int j=0;j<=md[to]-dep[to];j++) s[x][j+1]+=s[to][j];s[x][0]+=s[to][0];}for(int i=0;i<q[x].size();i++){int no=q[x][i].no,y=q[x][i].z;ans[no]+=1LL*(siz[x]-1)*min(dep[x]-1,y);ans[no]+=s[x][0]-siz[x]+1;if(y<md[x]-dep[x]) ans[no]-=s[x][y+1];} } int main() {freopen("longchain.in","r",stdin);freopen("longchain.out","w",stdout);scanf("%d%d",&n,&m);int x,y;for(int i=1;i<n;i++){scanf("%d%d",&x,&y);add(x,y); add(y,x);}for(int i=1;i<=m;i++){scanf("%d%d",&x,&y);q[x].push_back((query){i,y});}dfs1(1,0);s[1]=temp; temp+=md[1];dfs(1,0); for(int i=1;i<=m;i++) printf("%lld\n",ans[i]);return 0; }

2.CF1009F Dominant Indices

【題意】

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

【分析】

設計dp:

f[i][j]表示i子樹中到i 的距離為j 的點的個數

在dp轉移的時候，先做長兒子，每次處理完之后，直接把長兒子的信息向后錯一位放到當前的f數組中，然后再把其他子樹與當前暴力計算

我們在做dp的時候只對鏈的頂點申請內存，這樣節省了很多空間，只需要開能放下一條鏈的長度即可O(N)

對于u的長兒子v，給v 的內存分配到f[u]+1上 ，即f[v=son[u]]=f[u]+1

然后去計算其他兒子的答案，對于u的非長兒子，為他申請內存f[v]=now , now+=dep[u]，大小為v為頂端的長鏈長度

在dfs(v)之后，暴力合并信息即可

void dfs2(int u,int fa) {f[u][0]=1; // 先算上自己if (son[u]){f[son[u]]=f[u]+1; // 共享內存，這樣一步之后，f[son[u]][dep]會被自動保存到f[u][dep-1]dfs2(son[u],u);}for (int e=head[u];e;e=nex[e]){int v=tail[e];if (v==son[u] || v==fa) continue;f[v]=now;now+=dep[v]; // 為 v 節點申請內存，大小等于以 v 為頂端的長鏈的長度dfs2(v,u);for (int i=1;i<=dep[v];i++){f[u][i]+=f[v][i-1]; //暴力合并}} }

【代碼】

#include<bits/stdc++.h> using namespace std; const int maxn=3e5+5; typedef long long ll; int head[maxn],n,m,tot; ll siz[maxn],ans[maxn],tmp[maxn],*s[maxn],*temp=tmp; struct edge {int to,nxt; }e[maxn<<1]; void add(int x,int y) {e[++tot].to=y; e[tot].nxt=head[x]; head[x]=tot; } struct query {int no,z; }; vector <query> q[maxn]; int dep[maxn],son[maxn],md[maxn]; void dfs1(int x,int fa) {dep[x]=md[x]=dep[fa]+1; siz[x]=1;for(int i=head[x];i;i=e[i].nxt){int to=e[i].to;if(to==fa) continue;dfs1(to,x);siz[x]+=siz[to];if(md[to]>md[son[x]]) son[x]=to;}if(son[x]) md[x]=md[son[x]]; } void dfs(int x,int fa) {s[x][0]=siz[x]-1;if(son[x]) s[son[x]]=s[x]+1,dfs(son[x],x),s[x][0]+=s[son[x]][0];for(int i=head[x];i;i=e[i].nxt){int to=e[i].to;if(to==fa || to==son[x]) continue;s[to]=temp; temp+=md[to]-dep[to]+1;dfs(to,x);for(int j=0;j<=md[to]-dep[to];j++) s[x][j+1]+=s[to][j];s[x][0]+=s[to][0];}for(int i=0;i<q[x].size();i++){int no=q[x][i].no,y=q[x][i].z;ans[no]+=1LL*(siz[x]-1)*min(dep[x]-1,y);ans[no]+=s[x][0]-siz[x]+1;if(y<md[x]-dep[x]) ans[no]-=s[x][y+1];} } int main() {freopen("longchain.in","r",stdin);freopen("longchain.out","w",stdout);scanf("%d%d",&n,&m);int x,y;for(int i=1;i<n;i++){scanf("%d%d",&x,&y);add(x,y); add(y,x);}for(int i=1;i<=m;i++){scanf("%d%d",&x,&y);q[x].push_back((query){i,y});}dfs1(1,0);s[1]=temp; temp+=md[1];dfs(1,0); for(int i=1;i<=m;i++) printf("%lld\n",ans[i]);return 0; }

總結

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

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