Propagating tree

题意

给你一棵 个结点的树, 以 为根。每个结点有点权。有 次操作：

结点权值 ， 的儿子权值 ， 的孙子们 ，以此类推。

询问 的点权；

思路

又是单点查询，看看树状数组吧。区间修改就可以用差分。但是第一个操作有些麻烦，但这和每个节点的深度奇偶有关。所以只需判断一下深度，决定修改的值的正负就好，但是初始值不受影响，故还需用一个数组来存储初始值。

代码

#include<bits/stdc++.h>
#define ll long long
const int N=2e6+5,INF=0x3f3f3f3f,mod=998244353;
using namespace std;

int n,m,p,cnt,tot;
int l[N],r[N],tr[N],head[N],dep[N],val[N];
struct node
{
    int nxt,to;
}e[N<<1];

inline int read()
{
    register int x=0,f=1;char c=getchar();
    while(c<'0'||c>'9'){if(c=='-') f=-1;c=getchar();}
    while(c>='0'&&c<='9') x=(x<<3)+(x<<1)+(c^48),c=getchar();
    return x*f;
}

int qpow(int a,int b)
{
    int ans=1;
    while(b){if(b&1) ans=ans*a%mod;a=a*a%mod;b>>=1;}
    return ans;
}

void add(int u,int v)
{
    e[++cnt].nxt=head[u];
    e[cnt].to=v;
    head[u]=cnt;
}

int lowbit(int x)
{
    return x&(-x);
}

int ins(int x,int w){while(x<=n){tr[x]+=w;x+=lowbit(x);}}
int query(int x){int ans=0;while(x){ans+=tr[x];x^=lowbit(x);}return ans;}

void dfs(int u,int ***]=++tot;
    dep[u]=dep[fa]+1;
    for(int i=head[u];i;i=e[i].nxt)
    {
        int v=e[i].to;
        if(v==fa)    continue ;
        dfs(v,u);
    }
    r[u]=tot;
}

int main()
{
    n=read();m=read();
    for(int i=1;i<=n;i++) val[i]=read();
    for(int i=1;i<n;i++)
    {
        int u=read(),v=read();
        add(u,v);add(v,u);
    }
    dfs(1,0);
    for(int i=1;i<=m;i++)
    {
        int opt=read();
        if(opt==1)
        {
            int x=read(),y=read();
            if(dep[x]&1)    ins(l[x],y),ins(r[x]+1,-y);
            else ins(l[x],-y),ins(r[x]+1,y); 
        }
        else
        {
            int x=read();
            int y=query(l[x]);
            if(dep[x]&1)    printf("%d\n",val[x]+y);
            else printf("%d\n",val[x]-y);
        }
    }
    return 0;
}