题解 P3178 【[HAOI2015]树上操作】

· · 题解

这题其实可以在出栈入栈序上建立树状数组

由于一颗树根节点入栈与出栈序之间夹得是它的子树所以我们在该节点入栈的地方加上它的val出栈的时候减去它的val 之后查询x入栈到1的前缀和就是x节点到根的距离

给以某一节点 x 为根的子树在x节点上增加val会使该子树上所有的节点到根的距离都增加val

但是给以x节点为根的子树上的点都增加一个val, 每一个节点到根的距离增加的值不同我们就可以开第二个树状数组来维护输出t2.ask(x) * dis[x] + t1.ask(x)

具体操作请看代码

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstdlib>
#include<cstring>
#include<string>
#include<queue>
#include<ctime>
#include<deque>
#include<set>
#include<bitset>
#include<vector>
#include<list>
#include<stack>
#include<map>
#include<cmath>
#include<cctype>
#include<ctime>
#define ll long long
#define inf 99999999
#define int long long
#define N 101000
using namespace std;
inline ll read()
{
    ll res=0,bo=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')bo=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){res=(res<<1)+(res<<3)+ch-'0';ch=getchar();}
    return bo*res;
}
struct Eage{
    int to, nxt;
}eage[N << 1];//链式前向星 
int head[N], n, m, cnt, p, in[N], out[N], z[N], dis[N]; 
void add(int a, int b){
    eage[++cnt].to = b;
    eage[cnt].nxt = head[a];//加边 
    head[a] = cnt;
    return;
}
void dfs(int x, int fa){
    in[x] = ++p;// 求出入栈出栈序 
    dis[x] = dis[fa] + 1; //dis[x]指 x节点到根之间有多少个节点 
    for(int i = head[x]; i; i = eage[i].nxt){
        if(eage[i].to == fa) continue;
        dfs(eage[i].to, x); 
    } 
    out[x] = ++p;
}
struct Tree{
    ll tree[N << 1];//因为每个点一次入栈一次出栈所以要开双倍空间 
    inline void bulid(){
        for(int i = 1; i <= n; ++i){
            for(int j = in[i]; j <= n << 1; j += j & -j)//建树在它入栈时加上它的权值 
                tree[j] += z[i];
            for(int j = out[i]; j <= n << 1; j += j & -j)//出栈时减去它的权值这样就保证只有它的子树才能加上它的权值 
                tree[j] -= z[i]; 
        }
    }
    inline ll ask(int x){
        ll ans = 0;
        for(int i = in[x]; i; i -= i & -i)//查询前缀和就是它到root的距离 
            ans += tree[i];
        return ans;
    } 
    inline void change(int x, int k){
        for(int i = in[x]; i <= n << 1; i += i & -i)
            tree[i] += k; 
        for(int i = out[x]; i <= n << 1; i += i & -i)
            tree[i] -= k;
    }
}t1, t2; //开两树状数组 
signed main()
{
    n = read(); 
    m = read();
    for(int i = 1; i <= n; ++i)
        z[i] = read();
    for(int i = 1; i < n; ++i){
        int a = read();
        int b = read();
        add(a, b);//双向边 
        add(b, a);
    }
    dfs(1, 0);
    t1.bulid(); 
    for(int i = 1; i <= m; ++i){
        int a = read(), x = read();
        if(a == 1) t1.change(x, read());//直接加在储存每个点的权值的树状数组上
        if(a == 2) {
            int y = read();
            t1.change(x, (ll)-y * ((ll)dis[x] - 1));//由于子树的每个节点减去的权值都是一样的 
                //怕爆int
            t2.change(x, (ll)y);//每个节点加的权值不一样的加在第二个树状数组上 
        }
        if(a == 3){
            ll ans = 0;
            ans += t1.ask(x);
            ans += t2.ask(x) * (ll)dis[x];//由于已经减过 y * (dis[x] - 1)所以查询时直接加上 t2.ask(x) * dis[x] 即可 
            printf("%lld\n", ans);
        }
    }
    return 0;
}