P3178 [HAOI2015]树上操作

题目链接：https://www.luogu.org/problemnew/show/P3178

题目描述

有一棵点数为 N 的树，以点 1 为根，且树点有边权。然后有 M 个操作，分为三种：

操作 1 ：把某个节点 x 的点权增加 a 。
操作 2 ：把某个节点 x 为根的子树中所有点的点权都增加 a 。
操作 3 ：询问某个节点 x 到根的路径中所有点的点权和。

输入输出格式

输入格式：

第一行包含两个整数 N, M 。表示点数和操作数。
接下来一行 N 个整数，表示树中节点的初始权值。
接下来 N-1 行每行两个正整数 from, to ，表示该树中存在一条边 (from, to) 。
再接下来 M 行，每行分别表示一次操作。其中第一个数表示该操作的种类（ 1-3 ），之后接这个操作的参数（ x 或者 x a ）。

输出格式：

对于每个询问操作，输出该询问的答案。答案之间用换行隔开。

输入输出样例

输入样例#1：

输出样例#1：

题解：

这似乎是个熟练剖分模板题= =然而蒟蒻还没学过熟练剖分，所以用dfs序+线段树写了下，就当熟悉一下这些比较基本的数据结构吧。

这题用dfs序+线段树还是比较巧妙的，首先这是子树的问题嘛，我们可以考虑求一下dfs序，并且每个结点对应了一个管辖的区间in[x]~out[x]。

然后分析题目中的操作，我们主要的分析是从操作对一条链的影响来分析的：

第一个操作单点更新，那么我们就可以知道，以当前点x为根的子树的所有点，其到根节点的距离都为增加，那么我们利用dfs序的性质，将in[x]更新一下就行了，这样前缀和也是会增加相应值的。

第二个操作子树更新，由于这个题我们考虑的是更新对链的影响，那么可以知道，这个子树上的结点受到的影响主要取决前面有多少个结点。这里我们还是要巧妙运用dfs序的性质，在对相应区间进行更新时，更新的值为区间中"+"的个数减去区间中"-"的个数。这样在查询前缀和时就能正确地统计出答案（yy一下就好了）。

第三个查询当前点到根节点这条链的权值和，这里我们可以直接根据dfs序的性质查询前缀和就行了。

代码如下（lazy标记没处理好查了半年错）：

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const ll N = ;

ll n,m;

ll a[N];

struct Tree{

    ll l,r;

    ll lazy,sum;

}tre[N<<];

ll in[N],out[N],head[N],f[N<<];

ll c[N<<],num[N<<];

ll dfn,tot;

struct Edge{

    ll u,v,next;

}e[N<<];

void adde(ll u,ll v){

    e[tot].v=v;e[tot].next=head[u];head[u]=tot++;

}

void dfs(ll u,ll fa){

    in[u]=++dfn;

    num[dfn]=u;f[dfn]=;

    for(ll i=head[u];i!=-;i=e[i].next){

        ll v=e[i].v;

        if(v!=fa) dfs(v,u);

    }

    out[u]=++dfn;

    num[dfn]=u;f[dfn]=-;

}

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

    tre[rt].l=l;tre[rt].r=r;

    ll mid=(l+r)>>;

    if(l==r){

        tre[rt].sum=f[l]*a[num[l]];

        return ;

    }

    build(rt<<,l,mid);

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

    tre[rt].sum=tre[rt<<].sum+tre[rt<<|].sum;

}

void push_down(ll rt){

    ll lazy=tre[rt].lazy;

    tre[rt<<].sum+=lazy*(c[tre[rt<<].r]-c[tre[rt<<].l-]);

    tre[rt<<|].sum+=lazy*(c[tre[rt<<|].r]-c[tre[rt<<|].l-]);

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

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

    tre[rt].lazy=;

    return ;

}

void add(ll rt,ll id,ll z){

    ll l=tre[rt].l,r=tre[rt].r;

    if(l==id&&r==id){

        tre[rt].sum+=z;

        return ;

    }

    push_down(rt);

    ll mid=(l+r)>>;

    if(mid>=id) add(rt<<,id,z);

    else add(rt<<|,id,z);

    tre[rt].sum=tre[rt<<].sum+tre[rt<<|].sum;

    return ;

}

void update(ll rt,ll l,ll r,ll z){

    ll L=tre[rt].l,R=tre[rt].r;

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

        tre[rt].sum+=(c[R]-c[L-])*(ll)z;

        tre[rt].lazy+=z;

        return ;

    }

    if(tre[rt].lazy) push_down(rt);

    ll mid=(L+R)>>;

    if(l<=mid) update(rt<<,l,r,z);

    if(r>mid) update(rt<<|,l,r,z);

    tre[rt].sum=tre[rt<<].sum+tre[rt<<|].sum;

    return ;

}

ll query(ll rt,ll l,ll r){

    ll res = ;

    ll L=tre[rt].l,R=tre[rt].r;

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

        return tre[rt].sum;

    }

    if(tre[rt].lazy) push_down(rt);

    ll mid=(L+R)>>;

    if(l<=mid) res+=query(rt<<,l,r);

    if(r>mid) res+=query(rt<<|,l,r);

    return res ;

}

int main(){

    scanf("%lld%lld",&n,&m);

    for(ll i=;i<=n;i++) scanf("%lld",&a[i]);

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

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

        ll u,v;

        scanf("%lld%lld",&u,&v);

        adde(u,v);adde(v,u);

    }

    dfs(,-);

    for(ll i=;i<=dfn;i++) c[i]=c[i-]+f[i];

    build(,,*n);

    for(ll i=;i<=m;i++){

        ll op,x,z;

        scanf("%lld",&op);

        if(op==){

            scanf("%lld%lld",&x,&z);

            add(,in[x],z);

            add(,out[x],-z);

        }else if(op==){

            scanf("%lld%lld",&x,&z);

            update(,in[x],out[x],z);

        }else{

            scanf("%lld",&x);

            printf("%lld\n",query(,,in[x]));

        }

    }

    return ;

}

秒客网

洛谷P3178 [HAOI2015]树上操作（dfs序+线段树）

P3178 [HAOI2015]树上操作

题目描述

输入输出格式

输入输出样例

相关文章