求和

题意

给你一颗以 为根有 个节点的树，每个节点有一个点权。给你 次操作 ，操作有两种类型： 表示将节点 的权值加上 ；

表示求以 为根的子树上所有节点的和（包括 节点）；

分析

我们可以通过 序将一整棵子树上映射到序列中连续的一段上。所以问题就变成了，单点修改，区间和查询。直接用树状数组维护就好了。

代码

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

int n,m,rt,cnt;
int T[N],head[N],l[N],r[N],a[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);
}

void update(int x,int w)
{
    while(x<N)
    {
        T[x]+=w;
        x+=lowbit(x);
    }
}

int query(int x)
{
    int res=0;
    while(x)
    {
        res+=T[x];
        x-=lowbit(x);
    }
    return res;
}

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

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