[关闭]
@KirinBill 2018-01-25T09:40:15.000000Z 字数 38897 阅读 1373

点分治学习笔记

分治

目录

算法介绍

算法思想

算法流程

点分治和其它分治一样，都是递归进行的（虽然有非递归写法，但是反人类啊，没学会Orz），我们以处理点的子树为例：
1. 找到的子树的重心；
2. ，函数是计算子树中过的路径的贡献；
3. 遍历未访问过的儿子；
4. 对于每个，，函数这里是计算子树中过但是到时有一段路径是重复的（即不是简单路径）这种路径数，也就是减去重复；
5. 递归，分治计算的子树；

伪代码：

  1. //求重心
  2. void get_grt(int u,int fa);
  4. //计算
  5. int solve(int u,int dis);
  7. int treeDC(int u){
  8.     use[u]=true; //标记已经处理过了
  9.     int ret=solve(u,0); //计算经过u的路径
  10.     for(int i=he[u],v;i;i=ed[i].nex){
  11.         v=ed[i].to;
  12.         if(!use[v]){
  13.             //减去重复，但距离初值要带上这条边，
  14.             //这样才能表示路径中v到u这一段不是两条链，而是重叠了
  15.             ret-=solve(v,ed[i].w);
  16.             grt=0,sum_sz=sz[v]; //初始化重心，找到子树v的
  17.             get_grt(v,0);
  18.             ret+=treeDC(grt); //一定不能写成v，不然T上天！！！
  19.         }
  20.     }
  21.     return ret;
  22. }

求重心的代码：

  1. void get_grt(int u,int fa){
  2.     static int max_subT_sz[MAXN]={INT_MAX};
  3.     sz[u]=1,max_subT_sz[u]=0;
  4.     for(int i=he[u],v;i;i=ed[i].nex){
  5.         v=ed[i].to;
  6.         if(!use[v] && v!=fa){
  7.             get_grt(v,u);
  8.             sz[u]+=sz[v];
  9.             max_subT_sz[u]=max(max_subT_sz[u],sz[v]);
  10.         }
  11.     }
  12.     max_subT_sz[u]=max(max_subT_sz[u],sum_sz-sz[u]);
  13.     if(max_subT_sz[u]<max_subT_sz[grt]) grt=u;
  14. }

练习

普通点分治

1.[BZOJ 1468] Tree

代码：

  1. #include <cstdio>
  2. #include <algorithm>
  3. #include <climits>
  5. using std::sort;
  6. using std::max;
  8. const int MAXN=40005;
  9. int k;
  10. int grt,sum_sz;
  11. int he[MAXN];
  12. int de[MAXN],sz[MAXN];
  13. bool use[MAXN];
  15. struct line{int to,nex,w;}ed[MAXN<<1];
  17. inline void addE(int u,int v,int w){
  18.     static int cnt;
  19.     ed[++cnt]=(line){v,he[u],w};
  20.     he[u]=cnt;
  21. }
  23. //找到重心
  24. void get_grt(int u,int fa){
  25.     static int max_subT[MAXN]={INT_MAX};
  26.     sz[u]=1,max_subT[u]=0;
  27.     for(int i=he[u],v;i;i=ed[i].nex){
  28.         v=ed[i].to;
  29.         if(!use[v] && v!=fa){
  30.             get_grt(v,u);
  31.             sz[u]+=sz[v];
  32.             max_subT[u]=max(max_subT[u],sz[v]);
  33.         }
  34.     }
  35.     //无根树，翻过来的也是子树
  36.     max_subT[u]=max(max_subT[u],sum_sz-sz[u]);
  37.     //更新重心
  38.     if(max_subT[u]<max_subT[grt]) grt=u;
  39. }
  41. void DFS(int u,int fa,int de){
  42.     ::de[++::de[0]]=de;
  43.     for(int i=he[u],v;i;i=ed[i].nex){
  44.         v=ed[i].to;
  45.         if(!use[v] && v!=fa) DFS(v,u,de+ed[i].w);
  46.     }
  47. }
  49. inline int solve(int u,int _de){
  50.     de[0]=0;
  51.     DFS(u,0,_de);
  52.     sort(de+1,de+de[0]+1);
  53.     int l=1,r=de[0];
  54.     int ret=0;
  55.     while(l<r){
  56.         //l和l+1,l+2,...,r构成点对，不是区间长
  57.         if(de[l]+de[r]<=k) ret+=r-l,++l;
  58.         else --r;
  59.     }
  60.     return ret;
  61. }
  63. int treeDC(int u){
  64.     use[u]=true;
  65.     int ret=solve(u,0);
  66.     for(int i=he[u],v;i;i=ed[i].nex){
  67.         v=ed[i].to;
  68.         if(!use[v]){
  69.             //减去重复情况
  70.             ret-=solve(v,ed[i].w);
  71.             grt=0,sum_sz=sz[v];
  72.             get_grt(v,0);
  73.             ret+=treeDC(grt);
  74.         }
  75.     }
  76.     return ret;
  77. }
  79. int main(){
  80.     int n;
  81.     scanf("%d",&n);
  82.     for(int i=1,u,v,w;i<n;++i){
  83.         scanf("%d%d%d",&u,&v,&w);
  84.         addE(u,v,w),addE(v,u,w);
  85.     }
  86.     scanf("%d",&k);
  87.     sum_sz=n;
  88.     get_grt(1,0);
  89.     printf("%d",treeDC(grt));
  90.     return 0;
  91. }

2.[BZOJ 1316] 树上的询问

代码：

  1. #include <cstdio>
  2. #include <algorithm>
  3. #include <climits>
  5. using std::max;
  6. using std::sort;
  8. const int MAXN=10005,MAXQ=105;
  9. int q,grt,sum_sz;
  10. int he[MAXN],de[MAXN],sz[MAXN];
  11. int qry[MAXN],ans[MAXQ];
  12. bool use[MAXN];
  14. struct line{int to,nex,w;}ed[MAXN<<1];
  16. inline void addE(int u,int v,int w){
  17.     static int cnt;
  18.     ed[++cnt]=(line){v,he[u],w};
  19.     he[u]=cnt;
  20. }
  22. void get_grt(int u,int fa){
  23.     static int max_subT_sz[MAXN]={INT_MAX};
  24.     sz[u]=1,max_subT_sz[u]=0;
  25.     for(int i=he[u],v;i;i=ed[i].nex){
  26.         v=ed[i].to;
  27.         if(!use[v] && v!=fa){
  28.             get_grt(v,u);
  29.             sz[u]+=sz[v];
  30.             max_subT_sz[u]=max(max_subT_sz[u],sz[v]);
  31.         }
  32.     }
  33.     max_subT_sz[u]=max(max_subT_sz[u],sum_sz-sz[u]);
  34.     if(max_subT_sz[u]<max_subT_sz[grt]) grt=u;
  35. }
  37. void DFS(int u,int fa,int de){
  38.     ::de[++::de[0]]=de;
  39.     for(int i=he[u],v;i;i=ed[i].nex){
  40.         v=ed[i].to;
  41.         if(!use[v] && v!=fa) DFS(v,u,de+ed[i].w);
  42.     }
  43. }
  45. bool lt(int a,int b){return a<b;}
  47. bool leq(int a,int b){return a<=b;}
  49. inline int solve(int k,bool jud(int,int)){
  50.     int l=1,r=de[0],ret=0;
  51.     if(k==0) return jud(de[1],k);
  52.     while(l<r){
  53.         if(jud(de[l]+de[r],k)) ret+=r-l,++l;
  54.         else --r;
  55.     }
  56.     return ret;
  57. }
  59. void treeDC(int u){
  60.     use[u]=true;
  61.     de[0]=0;
  62.     DFS(u,0,0);
  63.     sort(de+1,de+de[0]+1);
  64.     for(int i=1;i<=q;++i)
  65.         ans[i]+=solve(qry[i],leq)-solve(qry[i],lt);
  66.     for(int i=he[u],v,w;i;i=ed[i].nex){
  67.         v=ed[i].to;
  68.         if(use[v]) continue;
  69.         w=ed[i].w;
  70.         de[0]=0;
  71.         DFS(v,0,ed[i].w);
  72.         sort(de+1,de+de[0]+1);
  73.         for(int j=1;j<=q;++j)
  74.             ans[j]-=solve(qry[j],leq)-solve(qry[j],lt);
  75.         grt=0,sum_sz=sz[v];
  76.         get_grt(v,0);
  77.         treeDC(grt);
  78.     }
  79. }
  81. int main(){
  82.     int n;
  83.     scanf("%d%d",&n,&q);
  84.     for(int i=1,u,v,w;i<n;++i){
  85.         scanf("%d%d%d",&u,&v,&w);
  86.         addE(u,v,w),addE(v,u,w);
  87.     }
  88.     for(int i=1;i<=q;++i)
  89.         scanf("%d",&qry[i]);
  90.     sum_sz=n;
  91.     get_grt(1,0);
  92.     treeDC(grt);
  93.     for(int i=1;i<=q;++i){
  94.         if(ans[i]) puts("Yes");
  95.         else puts("No");
  96.     }
  97.     return 0;
  98. }

3.[BZOJ 2152] 聪聪可可

代码：

  1. #include <cstdio>
  2. #include <algorithm>
  3. #include <climits>
  4. #include <cstring>
  6. using std::max;
  8. const int MAXN=20005;
  9. int grt,sum_sz;
  10. int he[MAXN];
  11. int sz[MAXN],de[MAXN],de_mod3[3];
  12. bool use[MAXN];
  14. struct line{int to,nex,w;}ed[MAXN<<1];
  16. inline int gcd(int a,int b){
  17.     int r;
  18.     while(b){
  19.         r=a%b;
  20.         a=b,b=r;
  21.     }
  22.     return a;
  23. }
  25. inline void addE(int u,int v,int w){
  26.     static int cnt;
  27.     ed[++cnt]=(line){v,he[u],w};
  28.     he[u]=cnt;
  29. }
  31. void get_grt(int u,int fa){
  32.     static int max_subT[MAXN]={INT_MAX};
  33.     sz[u]=1,max_subT[u]=0;
  34.     for(int i=he[u],v;i;i=ed[i].nex){
  35.         v=ed[i].to;
  36.         if(!use[v] && v!=fa){
  37.             get_grt(v,u);
  38.             sz[u]+=sz[v];
  39.             max_subT[u]=max(max_subT[u],sz[v]);
  40.         }
  41.     }
  42.     max_subT[u]=max(max_subT[u],sum_sz-sz[u]);
  43.     if(max_subT[u]<max_subT[grt]) grt=u;
  44. }
  46. void DFS(int u,int fa,int de){
  47.     ++de_mod3[de%3];
  48.     for(int i=he[u],v;i;i=ed[i].nex){
  49.         v=ed[i].to;
  50.         if(!use[v] && v!=fa)
  51.             DFS(v,u,de+ed[i].w);
  52.     }
  53. }
  55. inline int solve(int u,int _de){
  56.     memset(de_mod3,0,sizeof(de_mod3));
  57.     DFS(u,0,_de);
  58.     //两个人选，所以两个端点是两个方案
  59.     return de_mod3[0]*de_mod3[0]+(de_mod3[1]*de_mod3[2]<<1);
  60. }
  62. int treeDC(int u){
  63.     use[u]=true;
  64.     int ret=solve(u,0);
  65.     for(int i=he[u],v;i;i=ed[i].nex){
  66.         v=ed[i].to;
  67.         if(!use[v]){
  68.             ret-=solve(v,ed[i].w);
  69.             grt=0,sum_sz=sz[v];
  70.             get_grt(v,0);
  71.             ret+=treeDC(grt);
  72.         }
  73.     }
  74.     return ret;
  75. }
  77. int main(){
  78.     int n;
  79.     scanf("%d",&n);
  80.     for(int i=1,u,v,w;i<n;++i){
  81.         scanf("%d%d%d",&u,&v,&w);
  82.         addE(u,v,w),addE(v,u,w);
  83.     }
  84.     sum_sz=n;
  85.     get_grt(1,0);
  86.     int cnt=treeDC(grt),tot=n*n;
  87.     int gcd=::gcd(cnt,tot);
  88.     printf("%d/%d",cnt/gcd,tot/gcd);
  89.     return 0;
  90. }

4.[Codeforces 715C] Digit Tree

题目大意：给你一棵个点的树，每条边上有一个数字(~)，给出一个与互质的数，问整棵树上有多少条路径满足从起点走到终点的边上形成的十进制数是的倍数。.

代码：

  1. #include <cstdio>
  2. #include <algorithm>
  3. #include <climits>
  5. using std::max;
  6. using std::sort;
  7. using std::lower_bound;
  8. using std::upper_bound;
  10. const int MAXN=100005;
  11. int grt,m,sum_sz,tot;
  12. int he[MAXN],sz[MAXN];
  13. int de[MAXN],up[MAXN],dwn[MAXN];
  14. int pow10[MAXN];
  15. bool use[MAXN];
  17. struct line{int to,nex,w;}ed[MAXN<<1];
  19. inline void addE(int u,int v,int w){
  20.     static int cnt;
  21.     ed[++cnt]=(line){v,he[u],w};
  22.     he[u]=cnt;
  23. }
  25. int exgcd(int a,int &x,int b,int &y){
  26.     if(!b){
  27.         x=1,y=0;
  28.         return a;
  29.     }
  30.     int ret=exgcd(b,y,a%b,x);
  31.     y-=a/b*x;
  32.     return ret;
  33. }
  35. void get_grt(int u,int fa){
  36.     static int max_subT_sz[MAXN]={INT_MAX};
  37.     sz[u]=1,max_subT_sz[u]=0;
  38.     for(int i=he[u],v;i;i=ed[i].nex){
  39.         v=ed[i].to;
  40.         if(!use[v] && v!=fa){
  41.             get_grt(v,u);
  42.             sz[u]+=sz[v];
  43.             max_subT_sz[u]=max(max_subT_sz[u],sz[v]);
  44.         }
  45.     }
  46.     max_subT_sz[u]=max(max_subT_sz[u],sum_sz-sz[u]);
  47.     if(max_subT_sz[u]<max_subT_sz[grt]) grt=u;
  48. }
  50. void DFS(int u,int fa,int de,int up,int dwn){
  51.     ++tot;
  52.     ::de[tot]=de,::up[tot]=up,::dwn[tot]=dwn;
  53.     for(int i=he[u],v;i;i=ed[i].nex){
  54.         v=ed[i].to;
  55.         if(!use[v] && v!=fa)
  56.             DFS(v,u,de+1,(up+(long long)ed[i].w*pow10[de]%m)%m,((long long)dwn*10%m+ed[i].w)%m);
  57.     }
  58. }
  60. //ax=b mod c
  61. inline int equiv(int a,int b,int c){
  62.     int x,y;
  63.     exgcd(a,x,c,y);
  64.     return (long long)b*((x%c+c)%c)%c;
  65. }
  67. inline int cal_sum(int val){
  68.     return upper_bound(up+1,up+tot+1,val)-lower_bound(up+1,up+tot+1,val);
  69. }
  71. inline long long solve(int u,int _dis){
  72.     tot=0;
  73.     DFS(u,0,(bool)_dis,_dis%m,_dis%m);
  74.     sort(up+1,up+tot+1);
  75.     long long ret=0;
  76.     for(int i=1,up;i<=tot;++i){
  77.         up=equiv(pow10[de[i]],(-dwn[i]+m)%m,m);
  78.         ret+=cal_sum(up);
  79.     }
  80.     //此时，会多计算一个a=b=0的情况，也就是自己一个点
  81.     if(_dis==0) --ret;
  82.     return ret;
  83. }
  85. long long treeDC(int u){
  86.     use[u]=true;
  87.     long long ret=solve(u,0);
  88.     for(int i=he[u],v;i;i=ed[i].nex){
  89.         v=ed[i].to;
  90.         if(!use[v]){
  91.             ret-=solve(v,ed[i].w);
  92.             grt=0,sum_sz=sz[v];
  93.             get_grt(v,0);
  94.             ret+=treeDC(grt);
  95.         }
  96.     }
  97.     return ret;
  98. }
  100. int main(){
  101.     int n;
  102.     scanf("%d%d",&n,&m);
  103.     for(int i=1,u,v,w;i<n;++i){
  104.         scanf("%d%d%d",&u,&v,&w);
  105.         ++u,++v;
  106.         addE(u,v,w),addE(v,u,w);
  107.     }
  108.     pow10[0]=1;
  109.     for(int i=1;i<=n;++i)
  110.         pow10[i]=(long long)pow10[i-1]*10%m;
  111.     sum_sz=n;
  112.     get_grt(1,0);
  113.     printf("%I64d",treeDC(grt));
  114.     return 0;
  115. }

5.[BZOJ 3697] 采药人的路径

代码：

  1. #include <cstdio>
  2. #include <algorithm>
  3. #include <climits>
  4. #include <cmath>
  6. using std::max;
  7. using std::abs;
  9. const int MAXN=100005;
  10. int grt,sum_sz,max_dis;
  11. int he[MAXN],sz[MAXN];
  12. int tmp[2][MAXN<<1];
  13. int *have[2]={tmp[0]+MAXN,tmp[1]+MAXN};
  14. bool use[MAXN];
  16. struct line{int to,nex,w;}ed[MAXN<<1];
  18. inline void addE(int u,int v,int w){
  19.     static int cnt;
  20.     ed[++cnt]=(line){v,he[u],w};
  21.     he[u]=cnt;
  22. }
  24. void get_grt(int u,int fa){
  25.     static int max_subT_sz[MAXN]={INT_MAX};
  26.     sz[u]=1,max_subT_sz[u]=0;
  27.     for(int i=he[u],v;i;i=ed[i].nex){
  28.         v=ed[i].to;
  29.         if(!use[v] && v!=fa){
  30.             get_grt(v,u);
  31.             sz[u]+=sz[v];
  32.             max_subT_sz[u]=max(max_subT_sz[u],sz[v]);
  33.         }
  34.     }
  35.     max_subT_sz[u]=max(max_subT_sz[u],sum_sz-sz[u]);
  36.     if(max_subT_sz[u]<max_subT_sz[grt]) grt=u;
  37. }
  39. void DFS(int u,int fa,int dis){
  40.     static int tmp[MAXN<<1];
  41.     static int *pre=tmp+MAXN;
  42.     max_dis=max(max_dis,abs(dis));
  43.     ++have[(bool)pre[dis]][dis];
  44.     ++pre[dis];
  45.     for(int i=he[u],v;i;i=ed[i].nex){
  46.         v=ed[i].to;
  47.         if(!use[v] && v!=fa) DFS(v,u,dis+ed[i].w);
  48.     }
  49.     --pre[dis];
  50. }
  52. inline long long solve(int u){
  53.     static int tmp[2][MAXN<<1];
  54.     static int *sum_have[2]={tmp[0]+MAXN,tmp[1]+MAXN};
  55.     sum_have[0][0]=1;
  56.     max_dis=0;
  57.     long long ret=0;
  58.     for(int i=he[u],v;i;i=ed[i].nex){
  59.         v=ed[i].to;
  60.         if(use[v]) continue;
  61.         DFS(v,0,ed[i].w);
  62.         //休息站在重心上的
  63.         ret+=(long long)have[0][0]*(sum_have[0][0]-1);
  64.         for(int i=-max_dis;i<=max_dis;++i){
  65.             ret+=(long long)sum_have[1][i]*have[1][-i];
  66.             ret+=(long long)sum_have[0][i]*have[1][-i];
  67.             ret+=(long long)sum_have[1][i]*have[0][-i];
  68.         }
  69.         for(int i=-max_dis;i<=max_dis;++i){
  70.             sum_have[0][i]+=have[0][i];
  71.             sum_have[1][i]+=have[1][i];
  72.             have[0][i]=have[1][i]=0;
  73.         }
  74.     }
  75.     for(int i=-max_dis;i<=max_dis;++i)
  76.         sum_have[0][i]=sum_have[1][i]=0;
  77.     return ret;
  78. }
  80. long long treeDC(int u){
  81.     use[u]=true;
  82.     long long ret=solve(u);
  83.     for(int i=he[u],v;i;i=ed[i].nex){
  84.         v=ed[i].to;
  85.         if(!use[v]){
  86.             grt=0,sum_sz=sz[v];
  87.             get_grt(v,0);
  88.             ret+=treeDC(grt);
  89.         }
  90.     }
  91.     return ret;
  92. }
  94. int main(){
  95.     int n;
  96.     scanf("%d",&n);
  97.     for(int i=1,u,v,w;i<n;++i){
  98.         scanf("%d%d%d",&u,&v,&w);
  99.         if(w==0) w=-1;
  100.         addE(u,v,w),addE(v,u,w);
  101.     }
  102.     sum_sz=n;
  103.     get_grt(1,0);
  104.     printf("%lld",treeDC(grt));
  105.     return 0;
  106. }

6.[FJOI 2014] 最短路径树问题

代码：

  1. #include <cstdio>
  2. #include <algorithm>
  3. #include <climits>
  4. #include <queue>
  5. #include <vector>
  6. #include <functional>
  7. #include <cstring>
  9. using std::min;
  10. using std::max;
  11. using std::priority_queue;
  12. using std::vector;
  13. using std::greater;
  15. const int MAXN=30005,MAXM=60005;
  16. int n,k,ecnt;
  17. int grt,sum_sz;
  18. int ans,tot;
  19. int he[MAXN],sz[MAXN],dis[MAXN],pre[MAXN];
  20. int maxl[MAXN],cnt[MAXN]={1}; //深度为0的只有当前根这一个，且dis=0
  21. bool use[MAXN];
  23. struct line{int to,nex,w;}ed[MAXM<<1];
  24. struct node{
  25.     int id,dis;
  26.     node(int _id=0,int _dis=0):id(_id),dis(_dis){}
  27.     bool operator >(const node &that)const{
  28.         return dis>that.dis || (dis==that.dis && id>that.id);
  29.     }
  30. };
  32. inline void addE(int u,int v,int w){
  33.     static int &cnt=ecnt;
  34.     ed[++cnt]=(line){v,he[u],w};
  35.     he[u]=cnt;
  36. }
  38. inline void Dijkstra(){
  39.     static bool use[MAXN];
  40.     static priority_queue<node,vector<node>,greater<node> > hp;
  41.     memset(dis,0x7f,sizeof(dis));
  42.     dis[1]=0;
  43.     hp.push(node(1,0));
  44.     int u;
  45.     while(hp.size()){
  46.         u=hp.top().id;
  47.         hp.pop();
  48.         if(use[u]) continue;
  49.         use[u]=true;
  50.         for(int i=he[u],v,d;i;i=ed[i].nex){
  51.             v=ed[i].to,d=dis[u]+ed[i].w;
  52.             if(dis[v]>d){
  53.                 dis[v]=d,pre[v]=u;
  54.                 hp.push(node(v,d));
  55.             }
  56.         }
  57.     }
  58. }
  60. inline void rebuild(){
  61.     ecnt=0;
  62.     memset(he,0,sizeof(he));
  63.     for(int i=2,w;i<=n;++i){
  64.         w=dis[i]-dis[pre[i]];
  65.         addE(pre[i],i,w),addE(i,pre[i],w);
  66.     }
  67. }
  69. void get_grt(int u,int fa){
  70.     static int max_subT_sz[MAXN]={INT_MAX};
  71.     sz[u]=1,max_subT_sz[u]=0;
  72.     for(int i=he[u],v;i;i=ed[i].nex){
  73.         v=ed[i].to;
  74.         if(!use[v] && v!=fa){
  75.             get_grt(v,u);
  76.             sz[u]+=sz[v];
  77.             max_subT_sz[u]=max(max_subT_sz[u],sz[v]);
  78.         }
  79.     }
  80.     max_subT_sz[u]=max(max_subT_sz[u],sum_sz-sz[u]);
  81.     if(max_subT_sz[u]<max_subT_sz[grt]) grt=u;
  82. }
  84. void DFS_cal(int u,int fa,int de,int dis){
  85.     //点数=边数+1...
  86.     if(de>=k) return;
  87.     if(cnt[k-(de+1)]){
  88.         int d=dis+maxl[k-(de+1)];
  89.         if(d>ans) ans=d,tot=cnt[k-(de+1)];
  90.         else if(d==ans) tot+=cnt[k-(de+1)];
  91.     }
  92.     for(int i=he[u],v;i;i=ed[i].nex){
  93.         v=ed[i].to;
  94.         if(!use[v] && v!=fa)
  95.             DFS_cal(v,u,de+1,dis+ed[i].w);
  96.     }
  97. }
  99. void DFS_upd(int u,int fa,int de,int dis){
  100.     if(de>=k) return; //剪枝
  101.     if(dis>maxl[de]) maxl[de]=dis,cnt[de]=1;
  102.     else if(dis==maxl[de]) ++cnt[de];
  103.     for(int i=he[u],v;i;i=ed[i].nex){
  104.         v=ed[i].to;
  105.         if(!use[v] && v!=fa)
  106.             DFS_upd(v,u,de+1,dis+ed[i].w);
  107.     }
  108. }
  110. void treeDC(int u){
  111.     use[u]=true;
  112.     if(sum_sz<=k) return; //剪枝
  113.     memset(maxl+1,0,sum_sz<<2);
  114.     memset(cnt+1,0,sum_sz<<2);
  115.     for(int i=he[u],v;i;i=ed[i].nex){
  116.         v=ed[i].to;
  117.         if(!use[v]){
  118.             DFS_cal(v,0,1,ed[i].w);
  119.             DFS_upd(v,0,1,ed[i].w);
  120.         }
  121.     }
  122.     for(int i=he[u],v;i;i=ed[i].nex){
  123.         v=ed[i].to;
  124.         if(!use[v]){
  125.             grt=0,sum_sz=sz[v];
  126.             get_grt(v,0);
  127.             treeDC(grt);
  128.         }
  129.     }
  130. }
  132. int main(){
  133.     int m;
  134.     scanf("%d%d%d",&n,&m,&k);
  135.     for(int i=1,u,v,w;i<=m;++i){
  136.         scanf("%d%d%d",&u,&v,&w);
  137.         addE(u,v,w),addE(v,u,w);
  138.     }
  139.     Dijkstra();
  140.     rebuild();
  141.     sum_sz=n;
  142.     get_grt(1,0);
  143.     treeDC(grt);
  144.     printf("%d %d",ans,tot);
  145.     return 0;
  146. }

非递归版：[IOI 2011] Race

代码：

  1. #include <cstdio>
  2. #include <algorithm>
  3. #include <climits>
  4. #include <cstring>
  6. using std::min;
  7. using std::max;
  9. const int MAXN=200005,MAXK=1000005,INF=0x3f3f3f3f;
  10. int k,grt;
  11. int he[MAXN],fa[MAXN],de[MAXN],dis[MAXN];
  12. int minl[MAXK];
  13. int que[MAXN];
  14. int &bak=que[0];
  15. bool use[MAXN];
  17. struct line{int to,nex,w;}ed[MAXN<<1];
  19. inline void addE(int u,int v,int w){
  20.     static int cnt;
  21.     ed[++cnt]=(line){v,he[u],w};
  22.     he[u]=cnt;
  23. }
  25. inline void get_grt(int rt){
  26.     static int sz[MAXN],max_subT_sz[MAXN]={INT_MAX};
  27.     bak=0;
  28.     que[++bak]=rt;
  29.     for(int frt=1,u;frt<=bak;++frt){
  30.         u=que[frt];
  31.         sz[u]=1,max_subT_sz[u]=0;
  32.         for(int i=he[u],v;i;i=ed[i].nex){
  33.             v=ed[i].to;
  34.             if(use[v] || v==fa[u]) continue;
  35.             fa[v]=u;
  36.             que[++bak]=v;
  37.         }
  38.     }
  39.     grt=0;
  40.     for(int cur=bak,u,fa;cur;--cur){
  41.         u=que[cur],fa=::fa[u];
  42.         max_subT_sz[u]=max(max_subT_sz[u],bak-sz[u]);
  43.         //玄之又玄...
  44.         if(max_subT_sz[u]<=max_subT_sz[grt]) grt=u;
  45.         sz[fa]+=sz[u];
  46.         max_subT_sz[fa]=max(max_subT_sz[fa],sz[u]);
  47.         //solve的BFS从grt开始，
  48.         //与get_grt的顺序不同，
  49.         //要清一下
  50.         ::fa[u]=0;
  51.     }
  52. }
  54. inline void BFS(){
  55.     for(int frt=bak,u;frt<=bak;++frt){
  56.         u=que[frt];
  57.         for(int i=he[u],v;i;i=ed[i].nex){
  58.             v=ed[i].to;
  59.             if(use[v] || v==fa[u]) continue;
  60.             fa[v]=u;
  61.             dis[v]=dis[u]+ed[i].w,de[v]=de[u]+1;
  62.             que[++bak]=v;
  63.         }
  64.     }
  65. }
  67. inline int solve(){
  68.     bak=0;
  69.     int ret=INT_MAX;
  70.     for(int i=he[grt],u,lp;i;i=ed[i].nex){
  71.         u=ed[i].to;
  72.         if(use[u]) continue;
  73.         dis[u]=ed[i].w,de[u]=1;
  74.         que[++bak]=u,lp=bak;
  75.         BFS();
  76.         for(int cur=lp,v;cur<=bak;++cur){
  77.             v=que[cur];
  78.             if(dis[v]<=k) ret=min(ret,de[v]+minl[k-dis[v]]);
  79.         }
  80.         for(int cur=lp,v;cur<=bak;++cur){
  81.             v=que[cur];
  82.             if(dis[v]<=k) minl[dis[v]]=min(minl[dis[v]],de[v]);
  83.         }
  84.     }
  85.     return ret;
  86. }
  88. int treeDC(int rt){
  89.     use[rt]=true;
  90.     int ret=solve();
  91.     for(int cur=1,u;cur<=bak;++cur){
  92.         u=que[cur];
  93.         //原因同上
  94.         fa[u]=0;
  95.         //和虚树的类似，
  96.         //每次只清用到的，
  97.         //不要想复杂了。。。
  98.         if(dis[u]<=k) minl[dis[u]]=INF;
  99.     }
  100.     for(int i=he[rt],v;i;i=ed[i].nex){
  101.         v=ed[i].to;
  102.         if(!use[v]){
  103.             get_grt(v);
  104.             ret=min(ret,treeDC(grt));
  105.         }
  106.     }
  107.     return ret;
  108. }
  110. int main(){
  111.     int n;
  112.     scanf("%d%d",&n,&k);
  113.     for(int i=1,u,v,w;i<n;++i){
  114.         scanf("%d%d%d",&u,&v,&w);
  115.         ++u,++v;
  116.         addE(u,v,w),addE(v,u,w);
  117.     }
  118.     get_grt(1);
  119.     memset(minl+1,0x3f,sizeof(minl)-4);
  120.     int ans=treeDC(grt);
  121.     if(ans>=INF) ans=-1;
  122.     printf("%d",ans);
  123.     return 0;
  124. }

点分治序列：[BZOJ 3784] 树上的路径

代码：

  1. #include <cstdio>
  2. #include <algorithm>
  3. #include <climits>
  4. #include <queue>
  5. #include <cmath>
  6. #include <cstring>
  8. using std::max;
  9. using std::priority_queue;
  11. const int MAXN=50005;
  12. int idx,grt,sum_sz;
  13. int he[MAXN],sz[MAXN];
  14. int len[MAXN<<4],lp[MAXN<<4],rp[MAXN<<4];
  15. bool use[MAXN];
  17. struct line{int to,nex,w;}ed[MAXN<<1];
  18. struct chain{
  19.     int id,lp,rp,len;
  20.     chain(int _id=0,int _lp=0,int _rp=0,int _len=0):id(_id),lp(_lp),rp(_rp),len(_len){}
  21.     bool operator <(const chain &that)const{
  22.         return len<that.len;
  23.     }
  24. };
  25. priority_queue<chain> hp;
  27. class SparseTab{
  28.     private:
  29.         int c[20][MAXN<<4];
  30.     public:
  31.         void init(int a[],int n){
  32.             for(int i=1;i<=n;++i) c[0][i]=i;
  33.             for(int i=1,lim=log2(n);i<=lim;++i){
  34.                 for(int j=1;j+(1<<i)-1<=n;++j){
  35.                     if(len[c[i-1][j]]>len[c[i-1][j+(1<<i-1)]])
  36.                         c[i][j]=c[i-1][j];
  37.                     else c[i][j]=c[i-1][j+(1<<i-1)];
  38.                 }
  39.             }
  40.         }
  41.         int qry(int l,int r){
  42.             if(l>r) return 0;
  43.             int k=log2(r-l+1);
  44.             if(len[c[k][l]]>len[c[k][r-(1<<k)+1]])
  45.                 return c[k][l];
  46.             else return c[k][r-(1<<k)+1];
  47.         }
  48. }st;
  50. inline void addE(int u,int v,int w){
  51.     static int cnt;
  52.     ed[++cnt]=(line){v,he[u],w};
  53.     he[u]=cnt;
  54. }
  56. void get_grt(int u,int fa){
  57.     static int max_subT_sz[MAXN]={INT_MAX};
  58.     sz[u]=1,max_subT_sz[u]=0;
  59.     for(int i=he[u],v;i;i=ed[i].nex){
  60.         v=ed[i].to;
  61.         if(!use[v] && v!=fa){
  62.             get_grt(v,u);
  63.             sz[u]+=sz[v];
  64.             max_subT_sz[u]=max(max_subT_sz[u],sz[v]);
  65.         }
  66.     }
  67.     max_subT_sz[u]=max(max_subT_sz[u],sum_sz-sz[u]);
  68.     if(max_subT_sz[u]<max_subT_sz[grt]) grt=u;
  69. }
  71. void DFS(int u,int fa,int dis,int rp){
  72.     len[++idx]=dis;
  73.     lp[idx]=lp[idx-1],::rp[idx]=rp;
  74.     for(int i=he[u],v;i;i=ed[i].nex){
  75.         v=ed[i].to;
  76.         if(!use[v] && v!=fa) DFS(v,u,dis+ed[i].w,rp);
  77.     }
  78. }
  80. void treeDC(int u){
  81.     use[u]=true;
  82.     len[++idx]=0;
  83.     lp[idx]=rp[idx]=idx;
  84.     for(int i=he[u],v;i;i=ed[i].nex){
  85.         v=ed[i].to;
  86.         if(!use[v]) DFS(v,u,ed[i].w,idx);
  87.     }
  88.     for(int i=he[u],v;i;i=ed[i].nex){
  89.         v=ed[i].to;
  90.         if(!use[v]){
  91.             grt=0,sum_sz=sz[v];
  92.             get_grt(v,0);
  93.             treeDC(grt);
  94.         }
  95.     }
  96. }
  98. int main(){
  99.     int n,m;
  100.     scanf("%d%d",&n,&m);
  101.     for(int i=1,u,v,w;i<n;++i){
  102.         scanf("%d%d%d",&u,&v,&w);
  103.         addE(u,v,w),addE(v,u,w);
  104.     }
  105.     sum_sz=n;
  106.     get_grt(1,0);
  107.     treeDC(grt);
  108.     st.init(len,idx);
  109.     for(int i=1;i<=idx;++i){
  110.         if(lp[i]>rp[i]) continue;
  111.         hp.push(chain(i,lp[i],rp[i],len[i]+len[st.qry(lp[i],rp[i])]));
  112.     }
  113.     chain now;
  114.     for(int i=1,id,lp,rp,lmid,rmid,mid;i<=m;++i){
  115.         now=hp.top();
  116.         hp.pop();
  117.         printf("%d\n",now.len);
  118.         id=now.id,lp=now.lp,rp=now.rp;
  119.         mid=st.qry(lp,rp);
  120.         lmid=st.qry(lp,mid-1);
  121.         if(lmid) hp.push(chain(id,lp,mid-1,len[id]+len[lmid]));
  122.         rmid=st.qry(mid+1,rp);
  123.         if(rmid) hp.push(chain(id,mid+1,rp,len[id]+len[rmid]));
  124.     }
  125.     return 0;
  126. }

基环树分治：[BZOJ 3648] 寝室管理

代码：

  1. #include <cstdio>
  2. #include <algorithm>
  3. #include <climits>
  4. #include <cstring>
  6. using std::max;
  7. using std::sort;
  9. const int MAXN=100005;
  10. int n,grt,k,sum_sz,cut1,cut2;
  11. int he[MAXN],sz[MAXN],de[MAXN],cir[MAXN];
  12. bool use[MAXN];
  14. struct line{int to,nex;}ed[MAXN<<1];
  16. class rev_BIT{
  17.     private:
  18.         long long c[MAXN];
  19.         int lowbit(int x){return x&-x;}
  20.     public:
  21.         void add(int r){
  22.             for(;r;r-=lowbit(r)) ++c[r];
  23.         }
  24.         long long qry(int l){
  25.             //如果需要的剩下的长度非正了，
  26.             //说明这条链已经满足条件了，
  27.             //那么另一条链长度随意
  28.             if(l<=0) l=1;
  29.             long long ret=0;
  30.             for(;l<=n;l+=lowbit(l))
  31.                 ret+=c[l];
  32.             return ret;
  33.         }
  34. }ta;
  36. inline void addE(int u,int v){
  37.     static int cnt=1;
  38.     ed[++cnt]=(line){v,he[u]};
  39.     he[u]=cnt;
  40. }
  42. inline int revE(int i){return i^1;}
  44. bool find_cir(int u){
  45.     static int pre[MAXN];
  46.     static bool vis[MAXN];
  47.     vis[u]=true;
  48.     int fa=pre[u];
  49.     for(int i=he[u],v;i;i=ed[i].nex){
  50.         v=ed[i].to;
  51.         if(v==fa) continue;
  52.         if(vis[v]){
  53.             cut1=i,cut2=revE(i);
  54.             for(int now=u;now!=pre[v];now=pre[now])
  55.                 cir[++cir[0]]=now;
  56.             return true;
  57.         }
  58.         pre[v]=u;
  59.         if(find_cir(v)) return true;
  60.     }
  61.     return false;
  62. }
  64. void get_grt(int u,int fa){
  65.     static int max_subT_sz[MAXN]={INT_MAX};
  66.     sz[u]=1,max_subT_sz[u]=0;
  67.     for(int i=he[u],v;i;i=ed[i].nex){
  68.         if(i==cut1 || i==cut2) continue;
  69.         v=ed[i].to;
  70.         if(!use[v] && v!=fa){
  71.             get_grt(v,u);
  72.             sz[u]+=sz[v];
  73.             max_subT_sz[u]=max(max_subT_sz[u],sz[v]);
  74.         }
  75.     }
  76.     max_subT_sz[u]=max(max_subT_sz[u],sum_sz-sz[u]);
  77.     if(max_subT_sz[u]<max_subT_sz[grt]) grt=u;
  78. }
  80. void DFS(int u,int fa,int de){
  81.     ::de[++::de[0]]=de;
  82.     for(int i=he[u],v;i;i=ed[i].nex){
  83.         if(i==cut1 || i==cut2) continue;
  84.         v=ed[i].to;
  85.         if(!use[v] && v!=fa) DFS(v,u,de+1);
  86.     }
  87. }
  89. inline long long solve(int u,int _de){
  90.     de[0]=0;
  91.     DFS(u,0,_de);
  92.     sort(de+1,de+de[0]+1);
  93.     int l=1,r=de[0];
  94.     long long ret=0;
  95.     while(l<r){
  96.         if(de[l]+de[r]+1<k) ret+=r-l,++l;
  97.         else --r;
  98.     }
  99.     return ret;
  100. }
  102. long long treeDC(int u){
  103.     use[u]=true;
  104.     long long ret=solve(u,0);
  105.     for(int i=he[u],v;i;i=ed[i].nex){
  106.         if(i==cut1 || i==cut2) continue;
  107.         v=ed[i].to;
  108.         if(!use[v]){
  109.             ret-=solve(v,1);
  110.             grt=0,sum_sz=sz[v];
  111.             get_grt(v,0);
  112.             ret+=treeDC(grt);
  113.         }
  114.     }
  115.     return ret;
  116. }
  118. inline long long cal_cutE(){
  119.     memset(use,false,sizeof(use));
  120.     for(int i=1;i<=cir[0];++i)
  121.         use[cir[i]]=true;
  122.     long long ret=0;
  123.     for(int i=1,u;i<=cir[0];++i){
  124.         u=cir[i];
  125.         de[0]=0;
  126.         DFS(u,0,0);
  127.         for(int j=1;j<=de[0];++j) //绕一圈到cir[cir[0]]
  128.             ret+=ta.qry(k-(de[j]+(cir[0]-i+1)));
  129.         //两段中间是cir[1]和cir[cir[0]]，通过cut边相接
  130.         for(int j=1;j<=de[0];++j) //直接到cir[1]
  131.             ta.add(i+de[j]);
  132.     }
  133.     return ret;
  134. }
  136. int main(){
  137.     int m;
  138.     scanf("%d%d%d",&n,&m,&k);
  139.     for(int i=1,u,v;i<=m;++i){
  140.         scanf("%d%d",&u,&v);
  141.         addE(u,v),addE(v,u);
  142.     }
  143.     find_cir(1);
  144.     sum_sz=n;
  145.     get_grt(1,0);
  146.     long long ans=((long long)n*(n-1)>>1)-treeDC(grt);
  147.     if(m==n) ans+=cal_cutE();
  148.     printf("%lld",ans);
  149.     return 0;
  150. }

重心树维护动态点分治

1.[BZOJ 3730] 震波

代码：

  1. #include <cstdio>
  2. #include <algorithm>
  3. #include <climits>
  4. #include <cmath>
  5. #include <cstring>
  7. using std::max;
  8. using std::swap;
  10. const int MAXN=100005;
  11. int n,sum_sz,grt;
  12. int he[MAXN],val[MAXN],fa[MAXN];
  13. int dfn[MAXN<<1],pos[MAXN],de[MAXN];
  14. int sz[MAXN];
  15. bool use[MAXN];
  17. struct line{int to,nex;}ed[MAXN<<1];
  19. class SparseTab{
  20.     private:
  21.         int c[18][MAXN<<1];
  22.     public:
  23.         void init(int a[],int n){
  24.             memcpy(c[0]+1,a+1,n<<2);
  25.             for(int i=1,lim=log2(n);i<=lim;++i){
  26.                 for(int j=1;j+(1<<i)-1<=n;++j){
  27.                     if(de[c[i-1][j]]<de[c[i-1][j+(1<<i-1)]])
  28.                         c[i][j]=c[i-1][j];
  29.                     else c[i][j]=c[i-1][j+(1<<i-1)];
  30.                 }
  31.             }
  32.         }
  33.         int LCA(int u,int v){
  34.             u=pos[u],v=pos[v];
  35.             if(u>v) swap(u,v);
  36.             int k=log2(v-u+1);
  37.             if(de[c[k][u]]<de[c[k][v-(1<<k)+1]])
  38.                 return c[k][u];
  39.             else return c[k][v-(1<<k)+1];
  40.         }
  41. }st;
  42. class segT{
  43.     private:
  44.         struct node{
  45.             int sum;
  46.             node *ls,*rs;
  47.             node(){sum=0,ls=rs=NULL;}
  48.         }*rt;
  49.         void ist(node *&u,int l,int r,int pos,int val){
  50.             if(!u) u=new(node);
  51.             u->sum+=val;
  52.             if(l==r) return;
  53.             int mid=l+r>>1;
  54.             if(pos<=mid) ist(u->ls,l,mid,pos,val);
  55.             else ist(u->rs,mid+1,r,pos,val);
  56.         }
  57.         int qry(node *u,int l,int r,int lp,int rp){
  58.             if(!u) return 0;
  59.             if(lp<=l && r<=rp) return u->sum;
  60.             int mid=l+r>>1,ret=0;
  61.             if(lp<=mid) ret=qry(u->ls,l,mid,lp,rp);
  62.             if(rp>mid) ret+=qry(u->rs,mid+1,r,lp,rp);
  63.             return ret;
  64.         }
  65.     public:
  66.         void ist(int pos,int val){ist(rt,0,n,pos,val);}
  67.         int qry(int lp,int rp){return qry(rt,0,n,lp,rp);}
  68. }plus[MAXN],minus[MAXN];
  70. inline void addE(int u,int v){
  71.     static int cnt;
  72.     ed[++cnt]=(line){v,he[u]};
  73.     he[u]=cnt;
  74. }
  76. void DFS(int u,int fa){
  77.     de[u]=de[fa]+1;
  78.     dfn[++dfn[0]]=u;
  79.     pos[u]=dfn[0];
  80.     for(int i=he[u],v;i;i=ed[i].nex){
  81.         v=ed[i].to;
  82.         if(v!=fa){
  83.             DFS(v,u);
  84.             dfn[++dfn[0]]=u;
  85.         }
  86.     }
  87. }
  89. void get_grt(int u,int fa){
  90.     static int max_subT_sz[MAXN]={INT_MAX};
  91.     sz[u]=1,max_subT_sz[u]=0;
  92.     for(int i=he[u],v;i;i=ed[i].nex){
  93.         v=ed[i].to;
  94.         if(!use[v] && v!=fa){
  95.             get_grt(v,u);
  96.             sz[u]+=sz[v];
  97.             max_subT_sz[u]=max(max_subT_sz[u],sz[v]);
  98.         }
  99.     }
  100.     max_subT_sz[u]=max(max_subT_sz[u],sum_sz-sz[u]);
  101.     if(max_subT_sz[u]<max_subT_sz[grt]) grt=u;
  102. }
  104. void solve(int u,int fa,int de,segT &T){
  105.     T.ist(de,val[u]);
  106.     for(int i=he[u],v;i;i=ed[i].nex){
  107.         v=ed[i].to;
  108.         if(!use[v] && v!=fa)
  109.             solve(v,u,de+1,T);
  110.     }
  111. }
  113. void treeDC(int u){
  114.     use[u]=true;
  115.     solve(u,0,0,plus[u]);
  116.     for(int i=he[u],v;i;i=ed[i].nex){
  117.         v=ed[i].to;
  118.         if(!use[v]){
  119.             grt=0,sum_sz=sz[v];
  120.             get_grt(v,0);
  121.             fa[grt]=u;
  122.             solve(v,0,1,minus[grt]);
  123.             treeDC(grt);
  124.         }
  125.     }
  126. }
  128. inline int cal_dis(int u,int v){
  129.     return de[u]+de[v]-(de[st.LCA(u,v)]<<1);
  130. }
  132. inline int qry(int u,int k){
  133.     int ret=plus[u].qry(0,k);
  134.     for(int now=u,dis;fa[now];now=fa[now]){
  135.         dis=cal_dis(fa[now],u);
  136.         if(k<dis) continue;
  137.         ret+=plus[fa[now]].qry(0,k-dis);
  138.         ret-=minus[now].qry(0,k-dis);
  139.     }
  140.     return ret;
  141. }
  143. inline void mdf(int u,int val){
  144.     int dta=val-::val[u];
  145.     ::val[u]=val;
  146.     plus[u].ist(0,dta);
  147.     for(int now=u,dis;fa[now];now=fa[now]){
  148.         dis=cal_dis(fa[now],u);
  149.         plus[fa[now]].ist(dis,dta);
  150.         minus[now].ist(dis,dta);
  151.     }
  152. }
  154. int main(){
  155.     int m;
  156.     scanf("%d%d",&n,&m);
  157.     for(int i=1;i<=n;++i)
  158.         scanf("%d",&val[i]);
  159.     for(int i=1,u,v;i<n;++i){
  160.         scanf("%d%d",&u,&v);
  161.         addE(u,v),addE(v,u);
  162.     }
  163.     DFS(1,0);
  164.     st.init(dfn,dfn[0]);
  165.     sum_sz=n;
  166.     get_grt(1,0);
  167.     treeDC(grt);
  168.     for(int i=1,opt,x,y,lastans=0;i<=m;++i){
  169.         scanf("%d%d%d",&opt,&x,&y);
  170.         x^=lastans,y^=lastans;
  171.         if(opt==0){
  172.             lastans=qry(x,y);
  173.             printf("%d\n",lastans);
  174.         }
  175.         else mdf(x,y);
  176.     }
  177.     return 0;
  178. }

2.[BZOJ 4372] 烁烁的游戏

代码：

  1. #include <cstdio>
  2. #include <algorithm>
  3. #include <cstring>
  4. #include <climits>
  5. #include <cmath>
  7. using std::max;
  8. using std::swap;
  10. const int MAXN=1e5+5;
  11. int n,sum_sz,grt;
  12. int he[MAXN],sz[MAXN],fa[MAXN];
  13. int de[MAXN],dfn[MAXN<<1],pos[MAXN];
  14. bool use[MAXN];
  16. struct line{int to,nex;}ed[MAXN<<1];
  18. class SparseTab{
  19.     private:
  20.         int c[18][MAXN<<1];
  21.     public:
  22.         void init(int a[],int n){
  23.             memcpy(c[0]+1,a+1,n<<2);
  24.             for(int i=1,lim=log2(n);i<=lim;++i){
  25.                 for(int j=1;j+(1<<i)-1<=n;++j){
  26.                     if(de[c[i-1][j]]<de[c[i-1][j+(1<<i-1)]])
  27.                         c[i][j]=c[i-1][j];
  28.                     else c[i][j]=c[i-1][j+(1<<i-1)];
  29.                 }
  30.             }
  31.         }
  32.         int LCA(int u,int v){
  33.             u=pos[u],v=pos[v];
  34.             if(u>v) swap(u,v);
  35.             int k=log2(v-u+1);
  36.             if(de[c[k][u]]<de[c[k][v-(1<<k)+1]])
  37.                 return c[k][u];
  38.             else return c[k][v-(1<<k)+1];
  39.         }
  40. }st;
  41. class segT{
  42.     private:
  43.         struct node{
  44.             int sum;
  45.             node *ls,*rs;
  46.             node(){sum=0,ls=rs=NULL;}
  47.         }*rt;
  48.         void mdf(node *&u,int l,int r,int lp,int rp,int val){
  49.             if(!u) u=new(node);
  50.             if(lp<=l && r<=rp){
  51.                 u->sum+=val;
  52.                 return;
  53.             }
  54.             int mid=l+r>>1;
  55.             if(lp<=mid) mdf(u->ls,l,mid,lp,rp,val);
  56.             if(rp>mid) mdf(u->rs,mid+1,r,lp,rp,val);
  57.         }
  58.         int qry(node *u,int l,int r,int pos){
  59.             if(!u) return 0;
  60.             if(l==r) return u->sum;
  61.             int mid=l+r>>1,ret=u->sum;
  62.             if(pos<=mid) ret+=qry(u->ls,l,mid,pos);
  63.             else ret+=qry(u->rs,mid+1,r,pos);
  64.             return ret;
  65.         }
  66.     public:
  67.         void mdf(int lp,int rp,int val){mdf(rt,0,n,lp,rp,val);}
  68.         int qry(int pos){return qry(rt,0,n,pos);}
  69. }plus[MAXN],minus[MAXN];
  71. inline void addE(int u,int v){
  72.     static int cnt;
  73.     ed[++cnt]=(line){v,he[u]};
  74.     he[u]=cnt;
  75. }
  77. void DFS(int u,int fa){
  78.     de[u]=de[fa]+1;
  79.     dfn[++dfn[0]]=u;
  80.     pos[u]=dfn[0];
  81.     for(int i=he[u],v;i;i=ed[i].nex){
  82.         v=ed[i].to;
  83.         if(v!=fa){
  84.             DFS(v,u);
  85.             dfn[++dfn[0]]=u;
  86.         }
  87.     }
  88. }
  90. void get_grt(int u,int fa){
  91.     static int max_subT_sz[MAXN]={INT_MAX};
  92.     sz[u]=1,max_subT_sz[u]=0;
  93.     for(int i=he[u],v;i;i=ed[i].nex){
  94.         v=ed[i].to;
  95.         if(!use[v] && v!=fa){
  96.             get_grt(v,u);
  97.             sz[u]+=sz[v];
  98.             max_subT_sz[u]=max(max_subT_sz[u],sz[v]);
  99.         }
  100.     }
  101.     max_subT_sz[u]=max(max_subT_sz[u],sum_sz-sz[u]);
  102.     if(max_subT_sz[u]<max_subT_sz[grt]) grt=u;
  103. }
  105. void treeDC(int u){
  106.     use[u]=true;
  107.     for(int i=he[u],v;i;i=ed[i].nex){
  108.         v=ed[i].to;
  109.         if(!use[v]){
  110.             grt=0,sum_sz=sz[v];
  111.             get_grt(v,0);
  112.             fa[grt]=u;
  113.             treeDC(grt);
  114.         }
  115.     }
  116. }
  118. inline int cal_dis(int u,int v){
  119.     return de[u]+de[v]-(de[st.LCA(u,v)]<<1);
  120. }
  122. inline int qry(int u){
  123.     int ret=plus[u].qry(0);
  124.     for(int now=u,dis;fa[now];now=fa[now]){
  125.         dis=cal_dis(fa[now],u);
  126.         ret+=plus[fa[now]].qry(dis);
  127.         ret-=minus[now].qry(dis);
  128.     }
  129.     return ret;
  130. }
  132. inline void mdf(int u,int k,int w){
  133.     plus[u].mdf(0,k,w);
  134.     for(int now=u,dis;fa[now];now=fa[now]){
  135.         dis=cal_dis(fa[now],u);
  136.         if(dis>k) continue;
  137.         plus[fa[now]].mdf(0,k-dis,w);
  138.         minus[now].mdf(0,k-dis,w);
  139.     }
  140. }
  142. int main(){
  143.     int m;
  144.     scanf("%d%d",&n,&m);
  145.     for(int i=1,u,v;i<n;++i){
  146.         scanf("%d%d",&u,&v);
  147.         addE(u,v),addE(v,u);
  148.     }
  149.     DFS(1,0);
  150.     st.init(dfn,dfn[0]);
  151.     sum_sz=n;
  152.     get_grt(1,0);
  153.     treeDC(grt);
  154.     char opt;
  155.     for(int i=1,x,d,w;i<=m;++i){
  156.         scanf("\n%c%d",&opt,&x);
  157.         if(opt=='Q') printf("%d\n",qry(x));
  158.         else{
  159.             scanf("%d%d",&d,&w);
  160.             mdf(x,d,w);
  161.         }
  162.     }
  163.     return 0;
  164. }

3.[ZJOI 2015] 幻想乡战略游戏

代码：

  1. #include <cstdio>
  2. #include <algorithm>
  3. #include <cstring>
  4. #include <climits>
  5. #include <cmath>
  6. #include <vector>
  8. using std::max;
  9. using std::swap;
  10. using std::vector;
  12. const int MAXN=1e5+5;
  13. int grt,sum_sz;
  14. int he[MAXN],fa[MAXN],sz[MAXN];
  15. int lv[MAXN],dis[MAXN][19];
  16. int val_sum[MAXN];
  17. long long cost_sum[MAXN],tofa_cost[MAXN];
  18. bool use[MAXN];
  19. vector<int> T[MAXN],DCT[MAXN];
  21. struct line{int to,nex,w;}ed[MAXN<<1];
  23. inline void addE(int u,int v,int w){
  24.     static int cnt;
  25.     ed[++cnt]=(line){v,he[u],w};
  26.     he[u]=cnt;
  27. }
  29. void get_grt(int u,int fa){
  30.     static int max_subT_sz[MAXN]={INT_MAX};
  31.     sz[u]=1,max_subT_sz[u]=0;
  32.     for(int i=he[u],v;i;i=ed[i].nex){
  33.         v=ed[i].to;
  34.         if(!use[v] && v!=fa){
  35.             get_grt(v,u);
  36.             sz[u]+=sz[v];
  37.             max_subT_sz[u]=max(max_subT_sz[u],sz[v]);
  38.         }
  39.     }
  40.     max_subT_sz[u]=max(max_subT_sz[u],sum_sz-sz[u]);
  41.     if(max_subT_sz[u]<max_subT_sz[grt]) grt=u;
  42. }
  44. void DFS(int u,int fa,int lv){
  45.     for(int i=he[u],v;i;i=ed[i].nex){
  46.         v=ed[i].to;
  47.         if(!use[v] && v!=fa){
  48.             dis[v][lv]=dis[u][lv]+ed[i].w;
  49.             DFS(v,u,lv);
  50.         }
  51.     }
  52. }
  54. void treeDC(int u,int lv){
  55.     use[u]=true;
  56.     ::lv[u]=lv;
  57.     DFS(u,0,lv);
  58.     for(int i=he[u],v;i;i=ed[i].nex){
  59.         v=ed[i].to;
  60.         if(use[v]) continue;
  61.         T[u].push_back(v);
  62.         grt=0,sum_sz=sz[v];
  63.         get_grt(v,0);
  64.         fa[grt]=u;
  65.         DCT[u].push_back(grt);
  66.         treeDC(grt,lv+1);
  67.     }
  68. }
  70. inline void mdf(int u,int w){
  71.     for(int now=u;now;now=fa[now]){
  72.         val_sum[now]+=w;
  73.         cost_sum[now]+=(long long)w*dis[u][lv[now]];
  74.         tofa_cost[now]+=(long long)w*dis[u][lv[fa[now]]];
  75.     }
  76. }
  78. inline long long qry(int u){
  79.     long long ret=0;
  80.     for(int now=u;now;now=fa[now]){
  81.         ret+=cost_sum[now];
  82.         ret-=tofa_cost[now];
  83.         ret+=(long long)val_sum[now]*(dis[u][lv[now]]-dis[u][lv[fa[now]]]);
  84.     }
  85.     return ret;
  86. }
  88. long long solve(int u){
  89.     long long ret=qry(u);
  90.     for(int i=0,lim=T[u].size();i<lim;++i){
  91.         if(ret>qry(T[u][i]))
  92.             return solve(DCT[u][i]);
  93.     }
  94.     return ret;
  95. }
  97. int main(){
  98.     int n,q;
  99.     scanf("%d%d",&n,&q);
  100.     for(int i=1,u,v,w;i<n;++i){
  101.         scanf("%d%d%d",&u,&v,&w);
  102.         addE(u,v,w),addE(v,u,w);
  103.     }
  104.     sum_sz=n;
  105.     get_grt(1,0);
  106.     int grt=::grt;
  107.     treeDC(grt,1);
  108.     for(int i=1,u,e;i<=q;++i){
  109.         scanf("%d%d",&u,&e);
  110.         mdf(u,e);
  111.         printf("%lld\n",solve(grt));
  112.     }
  113.     return 0;
  114. }

可持久化重心树：[HNOI 2015] 开店

代码：

  1. #include <cstdio>
  2. #include <algorithm>
  3. #include <climits>
  5. using std::max;
  6. using std::swap;
  7. using std::sort;
  8. using std::lower_bound;
  9. using std::upper_bound;
  11. const int MAXN=150005;
  12. int n;
  14. struct monster{
  15.     int age,id;
  16.     monster(int _age=0,int _id=0):age(_age),id(_id){}
  17.     bool operator <(const monster &that)const{
  18.         return age<that.age;
  19.     }
  20.     static bool cmp_age(const monster &a,const monster &b){
  21.         return a.age<b.age;
  22.     }
  23. }devil[MAXN];
  25. class pDCT{
  26.     private:
  27.         int grt,sum_sz;
  28.         int he[MAXN],sz[MAXN];
  29.         int lv[MAXN],dis[MAXN][20],son_id[MAXN][20];
  30.         bool use[MAXN];
  31.         struct line{int to,nex,w;}ed[MAXN<<1];
  32.         void get_grt(int u,int fa){
  33.             static int max_subT_sz[MAXN]={INT_MAX};
  34.             sz[u]=1,max_subT_sz[u]=0;
  35.             for(int i=he[u],v;i;i=ed[i].nex){
  36.                 v=ed[i].to;
  37.                 if(!use[v] && v!=fa){
  38.                     get_grt(v,u);
  39.                     sz[u]+=sz[v];
  40.                     max_subT_sz[u]=max(max_subT_sz[u],sz[v]);
  41.                 }
  42.             }
  43.             max_subT_sz[u]=max(max_subT_sz[u],sum_sz-sz[u]);
  44.             if(max_subT_sz[u]<max_subT_sz[grt]) grt=u;
  45.         }
  46.         void DFS(int u,int fa,int lv){
  47.             for(int i=he[u],v;i;i=ed[i].nex){
  48.                 v=ed[i].to;
  49.                 if(!use[v] && v!=fa){
  50.                     son_id[v][lv]=son_id[u][lv];
  51.                     dis[v][lv]=dis[u][lv]+ed[i].w;
  52.                     DFS(v,u,lv);
  53.                 }
  54.             }
  55.         }
  56.         void treeDC(int u,int lv){
  57.             use[u]=true;
  58.             this->lv[u]=lv;
  59.             for(int i=he[u],v,idx=0;i;i=ed[i].nex){
  60.                 v=ed[i].to;
  61.                 if(!use[v]){
  62.                     son_id[v][lv]=idx++;
  63.                     dis[v][lv]=ed[i].w;
  64.                     DFS(v,0,lv);
  65.                     grt=0,sum_sz=sz[v];
  66.                     get_grt(v,0);
  67.                     treeDC(grt,lv+1);
  68.                 }
  69.             }
  70.         }
  71.     public:
  72.         void addE(int u,int v,int w){
  73.             static int cnt;
  74.             ed[++cnt]=(line){v,he[u],w};
  75.             he[u]=cnt;
  76.         }
  77.         void build(){
  78.             sum_sz=n;
  79.             get_grt(1,0);
  80.             treeDC(grt,1);
  81.         }
  82.     private:
  83.         struct node{
  84.             int node_cnt;
  85.             long long dis_sum,tofa_dis;
  86.             node *s[3];
  87.             node(){
  88.                 dis_sum=0;
  89.                 tofa_dis=node_cnt=0;
  90.                 s[0]=s[1]=s[2]=&Null;
  91.             }
  92.             node(node *u){*this=*u;}
  93.         }*rt[MAXN];
  94.         static node Null;
  95.     public:
  96.         pDCT(){rt[0]=&Null;}
  97.     private:
  98.         void ist(node *pre,node *&now,int u,int lv){
  99.             now=new node(pre);
  100.             now->dis_sum+=dis[u][lv];
  101.             now->tofa_dis+=dis[u][lv-1];
  102.             ++now->node_cnt;
  103.             if(lv!=this->lv[u])
  104.                 ist(pre->s[son_id[u][lv]],now->s[son_id[u][lv]],u,lv+1);
  105.         }
  106.         long long qry(node *now,int u,int lv){
  107.             if(now==&Null) return 0;
  108.             long long ret=0;
  109.             ret+=now->dis_sum;
  110.             ret-=now->tofa_dis;
  111.             ret+=(long long)now->node_cnt*(dis[u][lv]-dis[u][lv-1]);
  112.             if(lv!=this->lv[u])
  113.                 ret+=qry(now->s[son_id[u][lv]],u,lv+1);
  114.             return ret;
  115.         }
  116.         long long qry(int now,int u){return qry(rt[now],u,1);}
  117.     public:
  118.         void ist(int pre,int now,int u){ist(rt[pre],rt[now],u,1);}
  119.         long long qry(int l,int r,int u){return qry(r,u)-qry(l-1,u);}
  120. }T;
  121. pDCT::node pDCT::Null;
  123. inline void prepare(){
  124.     sort(devil+1,devil+n+1,monster::cmp_age);
  125.     for(int i=1;i<=n;++i)
  126.         T.ist(i-1,i,devil[i].id);
  127. }
  129. inline void find_his(int &l,int &r){
  130.     l=lower_bound(devil+1,devil+n+1,monster(l))-devil;
  131.     r=upper_bound(devil+1,devil+n+1,monster(r))-devil-1;
  132. }
  134. int main(){
  135.     int q,a;
  136.     scanf("%d%d%d",&n,&q,&a);
  137.     for(int i=1;i<=n;++i){
  138.         scanf("%d",&devil[i].age);
  139.         devil[i].id=i;
  140.     }
  141.     for(int i=1,u,v,w;i<n;++i){
  142.         scanf("%d%d%d",&u,&v,&w);
  143.         T.addE(u,v,w),T.addE(v,u,w);
  144.     }
  145.     T.build();
  146.     prepare();
  147.     long long lastans=0;
  148.     for(int i=1,u,l,r;i<=q;++i){
  149.         scanf("%d%d%d",&u,&l,&r);
  150.         l=(l+lastans)%a;
  151.         r=(r+lastans)%a;
  152.         if(l>r) swap(l,r);
  153.         find_his(l,r);
  154.         lastans=T.qry(l,r,u);
  155.         printf("%lld\n",lastans);
  156.     }
  157.     return 0;
  158. }

替罪羊树思想维护重心树：[WC 2014] 紫荆花之恋

代码：

  1. #include <cstdio>
  2. #include <algorithm>
  3. #include <cstdlib>
  4. #include <set>
  5. #include <stack>
  7. using std::swap;
  8. using std::set;
  9. using std::stack;
  11. const int MAXN=100005,MOD=1e9;
  12. int r[MAXN];
  14. class Treap{
  15. #define ls s[0]
  16. #define rs s[1]
  17.     public:
  18.         struct node{
  19.             int val,key,cnt,sz;
  20.             node *s[2];
  21.             node(){val=key=cnt=sz=0; s[0]=s[1]=Null;}
  22.             node(int _val):val(_val),key(rand()){
  23.                 cnt=sz=1,ls=rs=Null;
  24.             }
  25.             void* operator new(size_t){
  26.                 node *ret;
  27.                 if(mem_cur>mem_pool) ret=&*(mem_cur--);
  28.                 else ret=mem_bin.top(),mem_bin.pop();
  29.                 return ret;
  30.             }
  31.             void operator delete[](void *u){ //删除子树
  32.                 if(((node*)u)->ls!=Null) delete[](((node*)u)->ls);
  33.                 if(((node*)u)->rs!=Null) delete[](((node*)u)->rs);
  34.                 mem_bin.push((node*)u);
  35.             }
  36.             void upd(){sz= ls->sz + rs->sz + cnt;}
  37.         }*rt;
  38.         static node *Null;
  39.         Treap(){rt=Null;}
  40.     private:
  41.         static node mem_pool[MAXN*100];
  42.         static node *mem_cur;
  43.         static stack<node*> mem_bin;
  44.     private:
  45.         static node* rot(node *u,bool lr){
  46.             node *son=u->s[lr];
  47.             u->s[lr]=son->s[lr^1];
  48.             son->s[lr^1]=u;
  49.             u->upd(),son->upd();
  50.             return son;
  51.         }
  52.         static node* maintain(node *u,bool lr){
  53.             if(u->key > u->s[lr]->key)
  54.                 u=rot(u,lr);
  55.             return u;
  56.         }
  57.     public:
  58.         static void ist(node *&u,int val){
  59.             if(u==Null){
  60.                 u= new node(val);
  61.                 return;
  62.             }
  63.             if(u->val == val) ++u->cnt;
  64.             else{
  65.                 bool lr=(val > u->val);
  66.                 ist(u->s[lr],val);
  67.                 u=maintain(u,lr);
  68.             }
  69.             u->upd();
  70.         }
  71.         void ist(int val){ist(rt,val);}
  72.         void clear(){
  73.             if(rt!=Null) delete[](rt);
  74.             rt=Null;
  75.         }
  76.         int size(){return rt->sz;}
  77.         int lt_cnt(int val){ //小于val的值的个数
  78.             node *u=rt; int ret=0;
  79.             while(u!=Null){
  80.                 if(u->val <= val){
  81.                     ret+= u->ls->sz + u->cnt;
  82.                     u=u->rs;
  83.                 }
  84.                 else u=u->ls;
  85.             }
  86.             return ret;
  87.         }
  88. #undef ls
  89. #undef rs
  90. };
  91. Treap::node Treap::mem_pool[MAXN*100];
  92. Treap::node *Treap::Null=&mem_pool[0];
  93. Treap::node *Treap::mem_cur=Treap::mem_pool+(MAXN*100)-1;
  94. stack<Treap::node*> Treap::mem_bin;
  95. class SG_dync_DCT{
  96.     //pre T ↓
  97.     private:
  98.         int he[MAXN];
  99.         int anc[17][MAXN],dis[MAXN],de[MAXN];
  100.         struct line{int to,nex,w;}ed[MAXN<<1];
  101.         void addE(int u,int v,int w){
  102.             static int cnt;
  103.             ed[++cnt]=(line){v,he[u],w};
  104.             he[u]=cnt;
  105.         }
  106.         void prepare_LCA(int u,int fa){ //计算新加入的点的倍增数组
  107.             anc[0][u]=fa;
  108.             for(int i=1;i<17;++i)
  109.                 anc[i][u]=anc[i-1][anc[i-1][u]];
  110.         }
  111.         int LCA(int u,int v){
  112.             if(de[u]<de[v]) swap(u,v);
  113.             for(int d=de[u]-de[v],i=0;d;d>>=1,++i){
  114.                 if(d&1) u=anc[i][u];
  115.             }
  116.             if(u==v) return v;
  117.             for(int i=16;i>=0;--i){
  118.                 if(anc[i][u]!=anc[i][v])
  119.                     u=anc[i][u],v=anc[i][v];
  120.             }
  121.             return anc[0][u];
  122.         }
  123.         int cal_dis(int u,int v){
  124.             return dis[u]+dis[v]-(dis[LCA(u,v)]<<1);
  125.         }
  126.     public:
  127.         int ist(int u,int fa,int w){ //新加入u点
  128.             addE(u,fa,w),addE(fa,u,w);
  129.             de[u]=de[fa]+1,dis[u]=dis[fa]+w;
  130.             prepare_LCA(u,fa);
  131.             return upd(u,fa);
  132.         }
  133.     //DCT ↓
  134.     private:
  135.         static const double ALPHA;
  136.         int idx; //访问标号
  137.         int use[MAXN],vis[MAXN]; //用不用该点，该点这次重构是否访问过
  138.         int sz[MAXN];
  139.         int fa[MAXN]; //上层重心
  140.         set<int> dct[MAXN]; //重心树
  141.         Treap plus[MAXN],minus[MAXN]; //和之前的动态点分治套路一样
  142.         void DFS_del(int u){ //删除重心树的u的子树的treap和边
  143.             //因为只有这里是正常下去遍历整棵子树的，
  144.             //所以只能在这里标记等会可以到的点
  145.             //后面标记会gg，在treeDC里遍历是跳跃的，
  146.             //且这里只重建了一部分，没有重建的部分没有访问标记，
  147.             //遍历着会绕上去到不该重建的地方
  148.             use[u]=idx;
  149.             plus[u].clear();
  150.             for(set<int>::iterator iter=dct[u].begin();iter!=dct[u].end();++iter){
  151.                 minus[*iter].clear();
  152.                 DFS_del(*iter);
  153.             }
  154.             dct[u].clear();
  155.         }
  156.         int DFS_sz(int u,int fa){
  157.             sz[u]=1;
  158.             for(int i=he[u],v;i;i=ed[i].nex){
  159.                 v=ed[i].to;
  160.                 if(vis[v]!=idx && use[v]==idx && v!=fa)
  161.                     sz[u]+=DFS_sz(v,u);
  162.             }
  163.             return sz[u];
  164.         }
  165.         int get_grt(int u,int fa,int lim){
  166.             for(int i=he[u],v;i;i=ed[i].nex){
  167.                 v=ed[i].to;
  168.                 if(vis[v]!=idx && use[v]==idx && v!=fa){
  169.                     if(sz[v]>lim) return get_grt(v,u,lim);
  170.                 }
  171.             }
  172.             return u;
  173.         }
  174.         void DFS_ist(int u,int fa,int dis,Treap::node *&tp_rt){ //和3730那些一个套路
  175.             Treap::ist(tp_rt,dis-r[u]);
  176.             for(int i=he[u],v;i;i=ed[i].nex){
  177.                 v=ed[i].to;
  178.                 if(vis[v]!=idx && use[v]==idx && v!=fa)
  179.                     DFS_ist(v,u,dis+ed[i].w,tp_rt);
  180.             }
  181.         }
  182.         int treeDC(int u){ //这里由于有加点操作，treeDC()和之前略有不同
  183.             u=get_grt(u,0,DFS_sz(u,0)>>1);
  184.             vis[u]=idx;
  185.             DFS_ist(u,0,0,plus[u].rt);
  186.             Treap::node *minus_rt;
  187.             for(int i=he[u],v;i;i=ed[i].nex){
  188.                 v=ed[i].to;
  189.                 if(vis[v]!=idx && use[v]==idx){
  190.                     minus_rt=Treap::Null;
  191.                     DFS_ist(v,u,ed[i].w,minus_rt);
  192.                     v=treeDC(v);
  193.                     this->fa[v]=u;
  194.                     dct[u].insert(v);
  195.                     minus[v].rt=minus_rt;
  196.                 }
  197.             }
  198.             return u;
  199.         }
  200.         void rebuild(int u){
  201.             ++idx;
  202.             int fa=this->fa[u];
  203.             if(fa) dct[fa].erase(u);
  204.             DFS_del(u);
  205.             //这个treap是针对fa而算的，所以可以保留
  206.             //treeDC里的做法同理
  207.             Treap::node *minus_rt=minus[u].rt;
  208.             minus[u].rt=Treap::Null;
  209.             u=treeDC(u);
  210.             this->fa[u]=fa;
  211.             if(fa) dct[fa].insert(u);
  212.             minus[u].rt=minus_rt;
  213.         }
  214.         bool bal(int u){
  215.             return plus[u].size()<ALPHA*plus[fa[u]].size()+0.5;
  216.         }
  217.         void maintain(int u){
  218.             int cur=0;
  219.             for(;fa[u];u=fa[u]){
  220.                 if(!bal(u)) cur=fa[u];
  221.             }
  222.             if(cur) rebuild(cur);
  223.         }
  224.         int upd(int u,int fa){ //更新：计算u所带来的影响
  225.             this->fa[u]=fa;
  226.             dct[fa].insert(u);
  227.             int ret=0;
  228.             for(int now=u,r=::r[u],fa,dis;now;now=fa){
  229.                 fa=this->fa[now];
  230.                 if(fa){
  231.                     dis=cal_dis(u,fa);
  232.                     ret+=plus[fa].lt_cnt(r-dis);
  233.                     ret-=minus[now].lt_cnt(r-dis);
  234.                     minus[now].ist(dis-r);
  235.                 }
  236.                 plus[now].ist(cal_dis(u,now)-r);
  237.             }
  238.             maintain(u);
  239.             return ret;
  240.         }
  241. }DCT;
  242. const double SG_dync_DCT::ALPHA=0.88;
  244. int main(){
  245.     srand(125);
  246.     int n;
  247.     scanf("%*d%d",&n);
  248.     long long lastans=0;
  249.     for(int i=1,fa,w;i<=n;++i){
  250.         scanf("%d%d%d",&fa,&w,&r[i]);
  251.         fa^=lastans%MOD;
  252.         lastans+=DCT.ist(i,fa,w);
  253.         printf("%lld\n",lastans);
  254.     }
  255.     return 0;
  256. }
添加新批注
在作者公开此批注前，只有你和作者可见。
回复批注