P4315 月下“毛景树” （树链剖分+边剖分+区间覆盖+区间加+区间最大值）

题目链接：https://www.luogu.org/problem/P4315

题目大意：

有N个节点和N-1条树枝，但节点上是没有毛毛果的，毛毛果都是长在树枝上的。但是这棵“毛景树”有着神奇的魔力，他能改变树枝上毛毛果的个数：
Change k w：将第k条树枝上毛毛果的个数改变为w个。
Cover u v w：将节点u与节点v之间的树枝上毛毛果的个数都改变为w个。
Add u v w：将节点u与节点v之间的树枝上毛毛果的个数都增加w个。由于毛毛虫很贪，于是他会有如下询问：
Max u v：询问节点u与节点v之间树枝上毛毛果个数最多有多少个。

解题思路：一道边权树剖题，代码很长，调试起来还是有点复杂。

注意一下几点：

1.可以把边权转化为点权，因为每一个孩子节点通向父节点的边是唯一的，所以可以将每个边的边权转到边所连的孩子节点上（可在树剖的第一个dfs中完成）

2.修改一条链上的权值时，要注意链两端的点的lca不能够被修改，因为lca所对应的边权不在这一条链上。

3.Change 操作是修改第k条树枝，k为读入的顺序，而树的存边是双向的，所以要将读入的k乘以二在进行后面的操作。

4.下推标记的时候如果有覆盖标记不要忘了清除加的标记。

代码：

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

const int maxn=;

int tot,cnt,head[maxn],n,m,v[maxn];

ll tree[maxn*],lazy[maxn*],cov[maxn*];

int d[maxn],size[maxn],son[maxn],id[maxn],rk[maxn],fa[maxn],top[maxn];

//cov为覆盖标记，lazy为累加标记

struct Edge{

    int u,v,w,next;

}edge[maxn<<];

void add(int u,int v,int w){

    edge[++tot].v=v;

    edge[tot].u=u;

    edge[tot].w=w;

    edge[tot].next=head[u];

    head[u]=tot;

}

void dfs1(int u,int pre){

    d[u]=d[pre]+;

    fa[u]=pre;

    size[u]=;

    for(int i=head[u];i!=-;i=edge[i].next){

        int vv=edge[i].v;

        if(vv!=pre){

            dfs1(vv,u);

            size[u]+=size[vv];

            v[vv]=edge[i].w;  //边权转为点权

            if(size[son[u]]<size[vv]) son[u]=vv;

        }

    }

}

void dfs2(int u,int tp){

    top[u]=tp,id[u]=++cnt,rk[cnt]=u;

    if(son[u]) dfs2(son[u],tp);

    for(int i=head[u];i!=-;i=edge[i].next){

        int v=edge[i].v;

        if(v!=fa[u]&&v!=son[u]) dfs2(v,v);

    }

}

void pushup(int rt){

    tree[rt]=max(tree[rt<<],tree[rt<<|]);

}

void pushdown(int l,int r,int rt){

    if(cov[rt]!=-){

        cov[rt<<]=cov[rt<<|]=cov[rt];

        tree[rt<<]=tree[rt<<|]=cov[rt];

        lazy[rt<<]=lazy[rt<<|]=; //将孩子节点的lazy标记清0

        cov[rt]=-;

    }

    if(lazy[rt]){

        tree[rt<<]=tree[rt<<]+lazy[rt];

        tree[rt<<|]=tree[rt<<|]+lazy[rt];

        lazy[rt<<]+=lazy[rt];

        lazy[rt<<|]+=lazy[rt];

        lazy[rt]=;

    }

}

void build(int l,int r,int rt){

    lazy[rt]=;

    cov[rt]=-;

    if(l==r){

        tree[rt]=v[rk[l]];

        return;

    }

    int mid=l+r>>;

    build(l,mid,rt<<);

    build(mid+,r,rt<<|);

    pushup(rt);

}

void update1(int L,int R,int val,int l,int r,int rt){ //区间Cover和Change

    if(L<=l&&R>=r){

        tree[rt]=val;

        cov[rt]=val;

        lazy[rt]=; //将lazy标记清0

        return;

    }

    int mid=l+r>>;

    pushdown(mid-l+,r-mid,rt);

    if(mid>=L) update1(L,R,val,l,mid,rt<<);

    if(mid<R) update1(L,R,val,mid+,r,rt<<|);

    pushup(rt);

}

void update2(int L,int R,int val,int l,int r,int rt){ //区间Add

    if(L<=l&&R>=r){

        tree[rt]+=val;

        lazy[rt]+=val;

        return;

    }

    int mid=l+r>>;

    pushdown(mid-l+,r-mid,rt);

    if(mid>=L) update2(L,R,val,l,mid,rt<<);

    if(mid<R) update2(L,R,val,mid+,r,rt<<|);

    pushup(rt);

}

ll query(int L,int R,int l,int r,int rt){ //区间求Max

    if(L<=l&&R>=r) return tree[rt];

    int mid=l+r>>; ll res=;

    pushdown(mid-l+,r-mid,rt);

    if(mid>=L) res=max(res,query(L,R,l,mid,rt<<));

    if(mid<R) res=max(res,query(L,R,mid+,r,rt<<|));

    return res;

}

void updates1(int x,int y,int val){ //Cover

    while(top[x]!=top[y]){

        if(d[top[x]]<d[top[y]]) swap(x,y);

        update1(id[top[x]],id[x],val,,n,);

        x=fa[top[x]];

    }

    if(id[x]>id[y]) swap(x,y);

    update1(id[x]+,id[y],val,,n,); //不能更新lca所以是id[x]+1

}

void updates2(int x,int y,int val){ //Add

    while(top[x]!=top[y]){

        if(d[top[x]]<d[top[y]]) swap(x,y);

        update2(id[top[x]],id[x],val,,n,);

        x=fa[top[x]];

    }

    if(id[x]>id[y]) swap(x,y);

    update2(id[x]+,id[y],val,,n,); //不能更新lca所以是id[x]+1

}

ll ask(int x,int y){ //求Max

    ll res=;

    while(top[x]!=top[y]){

        if(d[top[x]]<d[top[y]]) swap(x,y);

        res=max(res,query(id[top[x]],id[x],,n,));

        x=fa[top[x]];

    }

    if(id[x]>id[y]) swap(x,y);

    res=max(res,query(id[x]+,id[y],,n,));

    return res;

}

int main(){

    scanf("%d",&n);

    memset(head,-,sizeof(head));

    cnt=,tot=;

    for(int i=;i<n;i++){

        int u,v,w;

        scanf("%d%d%d",&u,&v,&w);

        add(u,v,w); add(v,u,w);

    }

    dfs1(,),dfs2(,);

    build(,n,);

    while(true){

        char op[];

        int x,l,r,rt,val;

        scanf("%s",op);

        if(op[]=='t') break;

        if(op[]=='h'){

            scanf("%d%d",&x,&val); //因为是无向边，所以x*2表示的就是第x条边

            x=d[edge[x*].u]>d[edge[x*].v]?edge[x*].u:edge[x*].v;

            update1(id[x],id[x],val,,n,);  //Change操作

        } else if(op[]=='o'){

            scanf("%d%d%d",&l,&r,&val);

            updates1(l,r,val); //Cover操作

        } else if(op[]=='d'){

            scanf("%d%d%d",&l,&r,&val);

            updates2(l,r,val); //Add操作

        } else if(op[]=='a'){

            scanf("%d%d",&l,&r);

            printf("%lld\n",ask(l,r)); //Max操作

        }

    }

    return ;

}

巴特西

P4315 月下“毛景树” （树链剖分+边剖分+区间覆盖+区间加+区间最大值）

最新文章

热门文章