長鏈剖分

長鏈剖應用的場景必須是與子樹深度相關的，從這點上來講它是dsu on tree的特例。

解決的是某一結點對應子樹深度為k的結點的某些信息(如和)

與dsu on tree的不同：
?? ?1.L[](id[])數組含義仍不變，但R[]數組保存的是長鏈的最后一個結點對應的dfn
?? ?(不再是子樹最后一個結點對應的dfn)，son[u]保存的是u對應鏈最長兒子的編號?
?? ?2.不同長鏈的L,R都是沒有任何交集的，也就是說它們用于統計的數據結構是獨立的，而不像dsu on tree一樣是公用的，故在dsu中處理輕重兒子的順序就無關緊要了，可以先處理重兒子，再處理輕兒子。

#include <bits/stdc++.h>typedef long long ll; using namespace std;const int N=2e5+10; int h[N],to[2*N],ne[2*N],cnt; int dep[N],fa[N],son[N],len[N]; //用len數組用于保存長鏈的長度 int top[N],dfn,L[N],R[N],idx[N],skp; ll val[N],ans[N],sum[N*2]; int n,m; vector<pair<int,int>>lis[N]; void add_edge(int u,int v){to[cnt]=v;ne[cnt]=h[u];h[u]=cnt++; } void init(){cnt=0;memset(h,-1,sizeof(h)); } void dfs1(int u,int fat){dep[u]=dep[fat]+1;fa[u]=fat;for(int i=h[u];i!=-1;i=ne[i]){if(to[i]==fat)dfs1(to[i],u);if(!son[u]||len[son[u]]<len[to[i]])son[u]=to[i];}len[u]=len[son[u]]+1; }void dfs2(int u){L[u]=++dfn;R[u]=dfn+len[u]-1;idx[dfn]=u;//idx數組可有可無，不需要清空數據結構了，top數組也可有可無 if(son[u])dfs2(son[u]);for(int i=h[u];i!=-1;i=ne[i]){if(to[i]!=fa[u]&&to[i]!=son[u]){dfs2(to[i]);}} } void dsu(int u){//1.處理重兒子 if(son[u])dsu(son[u]);//2.處理輕兒子并同時把輕兒子往重兒子上并 for(int i=h[u];i!=-1;i=ne[i]){if(to[i]==fa[u]||to[i]==son[u])continue;dsu(to[i]); //輕兒子的起始點是對應u深度為1的點 for(int j=L[to[i]],k=1;j<=R[to[i]];j++,k++){sum[L[u]+k]+=sum[j];}}//加上自己 sum[L[u]]+=val[u];//3.計算答案 for(auto &i:lis[u]){ // if(L[u]+i.second>R[u]){ // ans[i.first]=0; // } // elseans[i.first]=sum[L[u]+i.second];}return; } int main(){init();scanf("%d",&n);for(int i=1;i<=n;++i){scanf("%lld",&val[i]);}int u,v; for(int i=2;i<=n;i++){scanf("%d%d",&u,&v);add_edge(u,v);add_edge(v,u);}dfs1(1,0);dfs2(1);scanf("%d",&m);int x,y;for(int i=1;i<=m;++i){scanf("%d %d",&x,&y);//以x為子節點深度為y的和 lis[x].push_back(make_pair(i,y));}dsu(1);for(int i=1;i<=m;++i){printf("%lld\n",ans[i]);}return 0; }

總結

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

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