【洛谷3384】树链剖分模板

题面

如题，已知一棵包含N个结点的树（连通且无环），每个节点上包含一个数值，需要支持以下操作：

操作1： 格式： 1 x y z 表示将树从x到y结点最短路径上所有节点的值都加上z

操作2： 格式： 2 x y 表示求树从x到y结点最短路径上所有节点的值之和

操作3： 格式： 3 x z 表示将以x为根节点的子树内所有节点值都加上z

操作4： 格式： 4 x 表示求以x为根节点的子树内所有节点值之和

代码

写挂的几个地方：跳链是跳到链端的父亲，比较深度也是比较链端的深度。

  1. #include<bits/stdc++.h>  
  2. using namespace std;  
  3. #define N 100010  
  4. #define lc (p<<1)  
  5. #define rc (p<<1|1)  
  6. #define ll long long  
  7. #define mid (t[p].l+t[p].r>>1)  
  8. ll n,m,op,cnt,tot,mod,root;  
  9. ll a[N],d[N],f[N],id[N],rk[N],son[N],siz[N],top[N],first[N];  
  10. struct email  
  11. {  
  12.     ll u,v;  
  13.     ll nxt;  
  14. }e[N*4];  
  15. void add(ll u,ll v)  
  16. {  
  17.     e[++cnt].nxt=first[u];first[u]=cnt;  
  18.     e[cnt].v=v;e[cnt].u=u;  
  19. }  
  20. struct tree  
  21. {  
  22.     ll l,r,sum,lazy;  
  23. }t[N*4];  
  24.   
  25. inline void pushnow(ll p,ll v)  
  26. {  
  27.     t[p].sum=(t[p].sum+(t[p].r-t[p].l+1)*v%mod)%mod;  
  28.     t[p].lazy=(v+t[p].lazy)%mod;   
  29. }  
  30.   
  31. inline void pushdown(ll p)  
  32. {  
  33.     if(t[p].lazy)  
  34.     {  
  35.         pushnow(lc,t[p].lazy);  
  36.         pushnow(rc,t[p].lazy);  
  37.         t[p].lazy=0;  
  38.     }  
  39. }  
  40.   
  41. inline void pushup(ll p)  
  42. {  
  43.     t[p].sum=(t[lc].sum+t[rc].sum)%mod;  
  44. }  
  45.   
  46. inline void build(ll p,ll l,ll r)  
  47. {  
  48.     t[p].l=l;t[p].r=r;  
  49.     if(l==r)  
  50.     {  
  51.         t[p].sum=a[rk[l]];  
  52.         return ;  
  53.     }  
  54.     ll bmid=l+r>>1;  
  55.     build(lc,l,bmid);build(rc,bmid+1,r);  
  56.     pushup(p);  
  57. }  
  58.   
  59. inline void update(ll p,ll ql,ll qr,ll v)  
  60. {  
  61.     if(ql<=t[p].l&&qr>=t[p].r)  
  62.     {  
  63.         pushnow(p,v);  
  64.         return ;   
  65.     }  
  66.     pushdown(p);  
  67.     if(ql<=mid)update(lc,ql,qr,v);  
  68.     if(qr>mid)update(rc,ql,qr,v);  
  69.     pushup(p);  
  70. }  
  71.   
  72. inline ll query(ll p,ll ql,ll qr)  
  73. {  
  74.     ll ret=0;  
  75.     if(ql<=t[p].l&&qr>=t[p].r)  
  76.         return t[p].sum;  
  77.     pushdown(p);  
  78.     if(ql<=mid)    ret=(ret+query(lc,ql,qr))%mod;  
  79.     if(qr>mid)    ret=(ret+query(rc,ql,qr))%mod;  
  80.     return ret;   
  81. }  
  82. inline void dfs1(ll u,ll fa,ll dep)  
  83. {  
  84.     d[u]=dep;f[u]=fa;siz[u]=1;  
  85.     for(ll i=first[u];i;i=e[i].nxt)  
  86.     {  
  87.         ll v=e[i].v;  
  88.         if(v==fa)continue;  
  89.         dfs1(v,u,dep+1);  
  90.         siz[u]+=siz[v];  
  91.         if(siz[v]>siz[son[u]])  
  92.             son[u]=v;  
  93.     }  
  94. }  
  95.   
  96. inline void dfs2(ll u,ll t)  
  97. {  
  98.     top[u]=t;id[u]=++tot;  
  99.     rk[tot]=u;  
  100.     if(son[u]==0)return;  
  101.     dfs2(son[u],t);  
  102.     for(ll i=first[u];i;i=e[i].nxt)  
  103.     {  
  104.         ll v=e[i].v;  
  105.         if(v!=f[u]&&v!=son[u])  
  106.             dfs2(v,v);  
  107.     }  
  108. }  
  109.   
  110. void updtree(ll x,ll y,ll v)  
  111. {  
  112.     ll fx=top[x],fy=top[y];  
  113.     while(fx!=fy)  
  114.     {  
  115.         if(d[fx]>=d[fy])  
  116.         {  
  117.             update(1,id[fx],id[x],v);  
  118.             x=f[fx];fx=top[x];  
  119.         }  
  120.         else  
  121.         {  
  122.             update(1,id[fy],id[y],v);  
  123.             y=f[fy];fy=top[y];  
  124.         }  
  125.     }  
  126.     if(id[x]<=id[y])update(1,id[x],id[y],v);  
  127.     else update(1,id[y],id[x],v);  
  128. }  
  129.   
  130. ll asktree(ll x,ll y)  
  131. {  
  132.     ll ret=0;  
  133.     ll fx=top[x],fy=top[y];  
  134.     while(fx!=fy)  
  135.     {  
  136.         if(d[fx]>=d[fy])  
  137.         {  
  138.             ret=(ret+query(1,id[fx],id[x]))%mod;  
  139.             x=f[fx];fx=top[x];  
  140.         }  
  141.         else  
  142.         {  
  143.             ret=(ret+query(1,id[fy],id[y]))%mod;  
  144.             y=f[fy];fy=top[y];  
  145.         }  
  146.     }  
  147.     if(id[x]<=id[y])ret=(ret+query(1,id[x],id[y]))%mod;  
  148.     else ret=(ret+query(1,id[y],id[x]))%mod;  
  149.     return ret%mod;  
  150. }  
  151.   
  152. int main()  
  153. {  
  154.     scanf("%lld%lld%lld%lld",&n,&m,&root,&mod);  
  155.     for(ll i=1;i<=n;i++)scanf("%lld",&a[i]);  
  156.     for(ll i=1;i<n;i++)  
  157.     {  
  158.         ll u,v;  
  159.         scanf("%lld%lld",&u,&v);  
  160.         add(u,v);add(v,u);  
  161.     }  
  162.     dfs1(root,0,1);  
  163.     dfs2(root,root);  
  164.     build(1,1,n);  
  165.     for(ll i=1;i<=m;i++)  
  166.     {  
  167.         ll x,y,z;  
  168.         scanf("%lld",&op);  
  169.         if(op==1)  
  170.         {  
  171.             scanf("%lld%lld%lld",&x,&y,&z);  
  172.             updtree(x,y,z);  
  173.         }   
  174.         if(op==2)  
  175.         {  
  176.             scanf("%lld%lld",&x,&y);  
  177.             printf("%lld ",asktree(x,y));  
  178.         }  
  179.         if(op==3)  
  180.         {  
  181.             scanf("%lld%lld",&x,&z);  
  182.             update(1,id[x],id[x]+siz[x]-1,z);  
  183.         }  
  184.         if(op==4)  
  185.         {  
  186.             scanf("%lld",&x);  
  187.             printf("%lld ",query(1,id[x],id[x]+siz[x]-1));  
  188.         }  
  189.     }   
  190.     return 0;  
  191. }  
【推广】 免费学中医，健康全家人
原文地址：https://www.cnblogs.com/NSD-email0820/p/9832127.html