洛谷P4315 月下“毛景树” 边权树剖+双标记

末蓝、 2023-06-04 07:59 45阅读 0赞

**[题目链接][Link 1]**

**做这道题的时候，乍一看很熟悉，之前考试时也做过类似的题。这道题树剖+线段树是个人都看得出来，不过覆盖标记和加标记同时下放是这道题最坑的地方。当时考试的时候就被这东西搞惨了。**

**做法：树剖维护边权的时候等效于维护两点之间深度较深的点的点权，这很好理解。![1596060-20190811172117244-1649484179.jpg][]**

**在修改和查询的时候，注意到这张图，我们假定修改F和G路径里的边权。这个时候我们同一般的树剖来跳，最后当他们在同一条链上时，其中有一个必然为另一个的祖先，但我们不能去改祖先的维护的那个点值，因为那个边没有在F->G的路径上。所以利用DFS序的连续性，要将祖先的DFS序+1，这样就改不到祖先那里去，只能改路径上的边权。同时下放两个标记的时候，覆盖标记的优先级是比加标记要大的，所以我们必须要先下放覆盖标记，而一旦有了覆盖标记，之前的所有标记全部作废，所以我们还要把加标记赋为0。并且要注意覆盖标记初始值为-1。**

**代码如下：**

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

1 #include<bits/stdc++.h>
      2 using namespace std;
      3 const int maxn=1e6+7;
      4 int n,x,y,v;
      5 struct node{
      6     int nxt,to,val,fro;
      7 }edge[maxn*3];
      8 struct node1{
      9     int l,r,lazy1,lazy2;
     10     long long sum,mx;
     11 }tree[maxn*4];
     12 int head[maxn],cnt;
     13 void add(int x,int y,int v){
     14     edge[++cnt].nxt=head[x];
     15     edge[cnt].fro=x;
     16     edge[cnt].to=y;
     17     edge[cnt].val=v;
     18     head[x]=cnt;
     19 }
     20 long long max(long long a,long long b){
     21     return a>b?a:b;
     22 }
     23 int dep[maxn],fa[maxn],top[maxn],size[maxn],son[maxn],id[maxn],rev[maxn],w[maxn];
     24 void dfs1(int x,int f){
     25     fa[x]=f;
     26     dep[x]=dep[f]+1;
     27     size[x]=1;
     28     int maxson=-1;
     29     for(int i=head[x];i;i=edge[i].nxt){
     30         int go=edge[i].to;
     31         if(go==fa[x]) continue;
     32         w[go]=edge[i].val;
     33         dfs1(go,x);
     34         size[x]+=size[go];
     35         if(size[go]>maxson){
     36             maxson=size[go];
     37             son[x]=go;
     38         }
     39     }
     40 }
     41 int Time;
     42 void dfs2(int x,int topf){
     43     top[x]=topf;
     44     id[x]=++Time;
     45     rev[id[x]]=w[x];
     46     if(!son[x]) return;
     47     dfs2(son[x],topf);
     48     for(int i=head[x];i;i=edge[i].nxt){
     49         int go=edge[i].to;
     50         if(son[x]==go||go==fa[x]) continue;
     51         dfs2(go,go);
     52     }
     53 }
     54 void build(int now,int l,int r){
     55     tree[now].l=l,tree[now].r=r,tree[now].lazy1=-1,tree[now].lazy2=0;
     56     if(l==r){
     57         tree[now].mx=rev[l];
     58         return;
     59     }
     60     int mid=(l+r)>>1;
     61     build(now<<1,l,mid);
     62     build(now<<1|1,mid+1,r);
     63     tree[now].mx=max(tree[now<<1].mx,tree[now<<1|1].mx);
     64 }
     65 void pushdown(int now){
     66     if(tree[now].lazy1!=-1){
     67         tree[now<<1].mx=tree[now].lazy1;
     68         tree[now<<1|1].mx=tree[now].lazy1; 
     69         tree[now<<1].lazy1=tree[now].lazy1;
     70         tree[now<<1|1].lazy1=tree[now].lazy1;
     71         tree[now].lazy1=-1;
     72         tree[now<<1].lazy2=tree[now<<1|1].lazy2=0;
     73     }
     74     if(tree[now].lazy2){
     75         tree[now<<1].mx+=tree[now].lazy2;
     76         tree[now<<1|1].mx+=tree[now].lazy2;
     77         tree[now<<1].lazy2+=tree[now].lazy2;
     78         tree[now<<1|1].lazy2+=tree[now].lazy2;
     79         tree[now].lazy2=0;
     80     }
     81 }
     82 void update1(int now,int l,int r,int v){
     83     if(tree[now].l>=l&&tree[now].r<=r){
     84         tree[now].lazy2+=v;
     85         tree[now].mx+=v;
     86         return; 
     87     }
     88     pushdown(now);
     89     int mid=(tree[now].l+tree[now].r)>>1;
     90     if(l<=mid) update1(now<<1,l,r,v);
     91     if(r>mid) update1(now<<1|1,l,r,v);
     92     tree[now].mx=max(tree[now<<1].mx,tree[now<<1|1].mx); 
     93 }
     94 void update2(int now,int l,int r,int v){
     95     if(tree[now].l>=l&&tree[now].r<=r){
     96         tree[now].mx=v;
     97         tree[now].lazy1=v;
     98         tree[now].lazy2=0;
     99         return;
    100     }
    101     pushdown(now);
    102     int mid=(tree[now].l+tree[now].r)>>1;
    103     if(l<=mid) update2(now<<1,l,r,v);
    104     if(r>mid) update2(now<<1|1,l,r,v);
    105     tree[now].mx=max(tree[now<<1].mx,tree[now<<1|1].mx);
    106 }
    107 long long query(int now,int l,int r){
    108     if(tree[now].l>=l&&tree[now].r<=r) return tree[now].mx;
    109     pushdown(now);
    110     int mid=(tree[now].l+tree[now].r)>>1;
    111     long long wa=0;
    112     if(l<=mid) wa=max(wa,query(now<<1,l,r));
    113     if(r>mid) wa=max(wa,query(now<<1|1,l,r));
    114     return wa; 
    115 }
    116 void link1(int x,int y,int v){
    117     while(top[x]!=top[y]){
    118         if(dep[top[x]]<dep[top[y]]) swap(x,y);
    119         update1(1,id[top[x]],id[x],v);
    120         x=fa[top[x]];
    121     }
    122     if(dep[x]<dep[y]) swap(x,y);
    123     update1(1,id[y]+1,id[x],v);
    124 }
    125 void link2(int x,int y,int v){
    126     while(top[x]!=top[y]){
    127         if(dep[top[x]]<dep[top[y]]) swap(x,y);
    128         update2(1,id[top[x]],id[x],v);
    129         x=fa[top[x]];
    130     }
    131     if(dep[x]<dep[y]) swap(x,y);
    132     update2(1,id[y]+1,id[x],v);
    133 }
    134 long long linkquery(int x,int y){
    135     if(x==y) return 0;
    136     long long ans=0;
    137     while(top[x]!=top[y]){
    138         if(dep[top[x]]<dep[top[y]]) swap(x,y);
    139         ans=max(ans,query(1,id[top[x]],id[x]));
    140         x=fa[top[x]];
    141     }
    142     if(dep[x]<dep[y]) swap(x,y);
    143     ans=max(ans,query(1,id[y]+1,id[x]));
    144     return ans;
    145 }
    146 char opt[5];
    147 int u,j,a,k;
    148 int main(){
    149     scanf("%d",&n);
    150     for(int i=1;i<n;i++){
    151         scanf("%d%d%d",&x,&y,&v);
    152         add(x,y,v);add(y,x,v);
    153     }
    154     dfs1(1,0);
    155     dfs2(1,1);
    156     build(1,1,n); 
    157     while(1){
    158         scanf("%s",opt);
    159         if(opt[0]=='C'&&opt[1]=='h'){
    160             scanf("%d%d",&k,&a);
    161             int x;
    162             x=dep[edge[k*2].fro]>dep[edge[k*2].to]?id[edge[k*2].fro]:id[edge[k*2].to];
    163             update2(1,x,x,a);
    164         }
    165         if(opt[0]=='C'&&opt[1]=='o'){
    166             scanf("%d%d%d",&u,&j,&a);
    167             link2(u,j,a);
    168         }
    169         if(opt[0]=='A'){
    170             scanf("%d%d%d",&u,&j,&a);
    171             link1(u,j,a);
    172         }
    173         if(opt[0]=='M'){
    174             scanf("%d%d",&u,&j);
    175             printf("%lld\n",linkquery(u,j));
    176         }
    177         if(opt[0]=='S') break;
    178     }
    179     return 0;
    180 }

转载于:https://www.cnblogs.com/LJB666/p/11335740.html

[Link 1]: https://www.luogu.org/problem/P4315
[1596060-20190811172117244-1649484179.jpg]: /images/20230601/60265f46d2e64312993441808921b148.png
[ContractedBlock.gif]: https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: /images/20230601/2d2ba37ad1e34ef098f66b2f877569b5.png