树链板子-白红宇的个人博客

树链板子

发布日期：2021-09-25 23:57:53 浏览次数：6 分类：技术文章

本文共 1994 字，大约阅读时间需要 6 分钟。

可以解决的问题：

(1)从 x 到 y 最短路径上的结点值 + z

(2)求从 x 到 y 最短路径的结点值之和

(3)以 x 为根节点的子树内，结点值 + z

(4)求以 x 为根节点的子树内，所有节点值之和

理一下思路吧。。贴板子贴多了今天自己写了写dfs有些信息写不全。。

第一个dfs解决的东西：因为是按照正常dfs顺序遍历的，所以可以记录一些树上的信息：深度大小 ( 计算重儿子 ) 找重儿子(为下面剖分指明方向) 记录父亲节点

第二个dfs解决的东西：划分轻重链，按照轻重链将树变成区间，既然变成区间了，那么还需要顺便把原来在树上的信息转换成区间信息。

#include
   
    #include
    
     #include
     
      #include
      
       #include
       #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             #include
             
              #include
              
               #define X first#define Y second#define L (u<<1)#define R (u<<1|1)#define Mid (tr[u].l+tr[u].r>>1)#define Len(u) (tr[u].r-tr[u].l+1)using namespace std;typedef long long LL;typedef pair
               
                 PII;const int N=100010,INF=0x3f3f3f3f;const double eps=1e-6;int n,m,root,mod;int in[N],depth[N],top[N],fa[N],son[N],se[N],tot;int e[N*2],ne[N*2],h[N],idx;int wt[N],w[N];LL ans;struct Node{ int l,r; LL sum,lazy;}tr[N<<2];void add(int a,int b){ e[idx]=b,ne[idx]=h[a],h[a]=idx++;}void dfs1(int u,int f,int d){ se[u]=1,depth[u]=d;//大小和深度 fa[u]=f;//父节点 int mx=-1; for(int i=h[u];~i;i=ne[i]) { int j=e[i]; if(j==f) continue; dfs1(j,u,d+1); se[u]+=se[j];//更新大小 if(mx
                
                 =l&&tr[u].r<=r) { tr[u].sum=(tr[u].sum+c*Len(u)%mod)%mod; tr[u].lazy=(tr[u].lazy+c)%mod; return; } pushdown(u); if(l<=Mid) modify(L,l,r,c); if(r>Mid) modify(R,l,r,c); pushup(u);}int query(int u,int l,int r){ if(tr[u].l>=l&&tr[u].r<=r) return tr[u].sum; pushdown(u); LL t=0; if(l<=Mid) t+=query(L,l,r); if(r>Mid) t=(t+query(R,l,r))%mod; return t%mod;}//询问void uprange(int x,int y,int z){ while(top[x]!=top[y]) { if(depth[top[x]]
                 
                  >n>>m>>root>>mod; for(int i=1;i<=n;i++) scanf("%d",&w[i]); for(int i=1;i<=n-1;i++) { int u,v; scanf("%d%d",&u,&v); add(u,v),add(v,u); } dfs1(root,-1,1); dfs2(root,root); build(1,1,n); while(m--) { int op,l,r; scanf("%d",&op); if(op==1) { int x,y,z; scanf("%d%d%d",&x,&y,&z); uprange(x,y,z); } else if(op==2) { int x,y; scanf("%d%d",&x,&y); qrange(x,y); } else if(op==3) { int x,y; scanf("%d%d",&x,&y); upson(x,y); } else { int x; scanf("%d",&x); qson(x); } } return 0;}/**/

转载地址：https://blog.csdn.net/DaNIelLAk/article/details/106444836 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！

上一篇：牛客 Yet Another Bracket Sequence 线段树

下一篇：POJ - 2728 Desert King 最小生成树 + 01分数规划

发表评论

关于作者

喝酒易醉，品茶养心，人生如梦，品茶悟道，何以解忧？唯有杜康！

-- 愿君每日到此一游！

发表评论

最新留言

关于作者

推荐文章