NC204871 求和

链接

思路：

        对于一个子树来说，子树的节点就包括在整颗树的dfs序中子树根节点出现的前后之间，所以我们先进行一次dfs，用b数组的0表示区间左端点，1表示区间右端点，同时用a数组来标记dfs序中的值。处理完dfs序后，我们就用dfs序列来建树，若要查询或修改一个子树，则区间就是b0到b1，由于在dfs序列中每个数都会出现两次，所以查询的结果是正确答案的两倍，我们只需要最后除以2即可。

 代码：

#include<bits/stdc++.h>
using namespace std;
const int N=2e6+10;
const int inf=0x3f3f3f3f;
typedef long long ll;
typedef pair<int,int> pii;
typedef unsigned long long ull;
//#define int long long
//const ll P=2281701377;
const ll P=998244353;
const int mod=1e9+7;int n,m,k,a[N],cnt,b[N][2],va[N];
vector<int> v[N];
ll tree[N*4];
void dfs(int x,int f){b[x][0]=++cnt;a[cnt]=x;for(auto y:v[x]){if(y==f) continue;dfs(y,x);} b[x][1]=++cnt;a[cnt]=x;
}
void build(int p,int l,int r){if(l==r){tree[p]=va[a[l]];return;}int mid=(l+r)>>1;build(p<<1,l,mid);build(p<<1|1,mid+1,r);tree[p]=tree[p<<1]+tree[p<<1|1];
}
void modify(int p,int l,int r,int a,int x){if(l==r&&l==a){tree[p]+=x;return;}int mid=(l+r)>>1;if(a<=mid) modify(p<<1,l,mid,a,x);else modify(p<<1|1,mid+1,r,a,x);tree[p]=tree[p<<1]+tree[p<<1|1];
}
ll query(int p,int l,int r,int x,int y){if(l>=x&&r<=y){return tree[p];}int mid=(l+r)>>1;ll res=0;if(x<=mid) res+=query(p<<1,l,mid,x,y);if(y>mid) res+=query(p<<1|1,mid+1,r,x,y);tree[p]=tree[p<<1]+tree[p<<1|1];return res;
}
void solve(){cin>>n>>m>>k;for(int i=1;i<=n;i++){cin>>va[i];}for(int i=1;i<n;i++){int a,b;cin>>a>>b;v[a].push_back(b);v[b].push_back(a);}dfs(k,0);build(1,1,cnt);while(m--){int f,a;cin>>f>>a;if(f==1){int x;cin>>x;modify(1,1,cnt,b[a][0],x);modify(1,1,cnt,b[a][1],x);}else{cout<<query(1,1,cnt,b[a][0],b[a][1])/2<<endl;}}}
signed main(){ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);int t=1;// cin>>t;while(t--){solve();}}