P4315 月下“毛景树” 树剖边权转点权-白红宇的个人博客

P4315 月下“毛景树” 树剖边权转点权

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

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

学了下边权转点权，做了下这个马虎一丢丢就一个测试点过不去的题。

边权转点权的时候，只需要把边权对应到更深的那个点即可。

更新操作的最后一步，也就是在他们都在一条链的时候，需要减去他们的 lca ，因为 lca 表示的边权不在两点之间。

操作很容易，码量实在有点多了，细节也比较多。

因为要实现区间赋值和区间加值，那么对于两种的lazy来说，赋值的lazy需要设为 -1 ，加值的 lazy 需要设为 0 。而且在pushdown的时候，需要先看看有没有赋值，有的话需要把该节点的加值的lazy 赋值为 0 ，因为赋值覆盖掉了前面加的数。

~~下面就是愉快的敲模板环节了~~

#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,mod=1e9+7,INF=0x3f3f3f3f;const double eps=1e-6;int n;int e[N*2],ne[N*2],w[N*2],h[N],idx;int wf[N];int depth[N],top[N],fa[N],se[N],son[N],in[N],wt[N],tot;struct query//因为要修改第几条链，所以直接存下来就好了{ int a,b,c;}q[N];struct Node{ int l,r; LL mx,lz,lazy;}tr[N<<2];void add(int a,int b,int c){ e[idx]=b,w[idx]=c,ne[idx]=h[a],h[a]=idx++;}void dfs1(int u,int f,int d,int ww){ depth[u]=d,fa[u]=f,wf[u]=ww; 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,w[i]); se[j]+=se[u]; if(se[j]>mx) mx=se[j],son[u]=j; }}void dfs2(int u,int t){ top[u]=t,in[u]=++tot; wt[tot]=wf[u]; if(son[u]==0) return; dfs2(son[u],t); for(int i=h[u];~i;i=ne[i]) { int j=e[i]; if(j==fa[u]||j==son[u]) continue; dfs2(j,j); }}void pushup(int u){ tr[u].mx=max(tr[L].mx,tr[R].mx);}void pushdown1(int u){ if(tr[u].lz==-1) return; tr[L].lazy=tr[R].lazy=0; tr[L].lz=tr[R].lz=tr[u].lz; tr[L].mx=tr[R].mx=tr[u].lz; tr[u].lz=-1;}void pushdown2(int u){ tr[L].lazy+=tr[u].lazy,tr[R].lazy+=tr[u].lazy; tr[L].mx+=tr[u].lazy,tr[R].mx+=tr[u].lazy; tr[u].lazy=0;}void build(int u,int l,int r){ tr[u]={ l,r,0,-1,0}; if(l==r) { tr[u].mx=wt[l]; return; } build(L,l,Mid),build(R,Mid+1,r); pushup(u);}void modify1(int u,int l,int r,LL c)//区间赋值{ if(tr[u].l>=l&&tr[u].r<=r) { tr[u].mx=c; tr[u].lz=c; tr[u].lazy=0; return; } pushdown1(u); pushdown2(u); if(l<=Mid) modify1(L,l,r,c); if(r>Mid) modify1(R,l,r,c); pushup(u);}void modify2(int u,int l,int r,LL c)//加值{ if(tr[u].l>=l&&tr[u].r<=r) { tr[u].lazy+=c; tr[u].mx+=c; return; } pushdown1(u),pushdown2(u); if(l<=Mid) modify2(L,l,r,c); if(r>Mid) modify2(R,l,r,c); pushup(u);}LL query(int u,int l,int r){ if(tr[u].l>=l&&tr[u].r<=r) return tr[u].mx; pushdown1(u),pushdown2(u); LL ans=0; if(l<=Mid) ans=max(ans,query(L,l,r)); if(r>Mid) ans=max(ans,query(R,l,r)); return ans;}void date1(int k,LL x){ int a=q[k].a,b=q[k].b; if(a==fa[b]) swap(a,b);//找深度更深的点 modify1(1,in[a],in[a],x);}void date2(int x,int y,LL c){ while(top[x]!=top[y]) { if(depth[top[x]]
                
                 depth[y]) swap(x,y); modify1(1,in[x]+1,in[y],c);//最后需要去掉lca，所以直接编号+1即可。}void date3(int x,int y,LL c){ while(top[x]!=top[y]) { if(depth[top[x]]
                 
                  depth[y]) swap(x,y); modify2(1,in[x]+1,in[y],c);//同上}LL qrange(int x,int y){ LL ans=0; while(top[x]!=top[y]) { if(depth[top[x]]
                  
                   depth[y]) swap(x,y); ans=max(ans,query(1,in[x]+1,in[y]));//同上 return ans;}int main(){ // ios::sync_with_stdio(false);// cin.tie(0); memset(h,-1,sizeof (h)); cin>>n; for(int i=1;i<=n-1;i++) { int a,b,c; scanf("%d%d%d",&a,&b,&c); add(a,b,c),add(b,a,c); q[i]={ a,b,c}; } dfs1(1,-1,1,0); dfs2(1,1); build(1,1,n); string op; while(cin>>op&&op!="Stop") { int a,b; scanf("%d%d",&a,&b); if(op[0]=='M') printf("%lld\n",qrange(a,b)); else if(op[0]=='A') { LL x; scanf("%lld",&x); date3(a,b,x); } else if(op[1]=='o') { LL x; scanf("%lld",&x); date2(a,b,x); } else date1(a,1ll*b); } return 0;}

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

上一篇：P4198 楼房重建线段树 + 单调栈

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

发表评论

关于作者

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

-- 愿君每日到此一游！

发表评论

最新留言

关于作者

推荐文章