C++11(clang++ 3.9) 解法, 执行用时: 1638ms, 内存消耗: 116552K, 提交时间: 2020-04-18 19:32:42

#include<bits/stdc++.h>
using namespace std;

int n,m,k,tot=0,in[1000005],out[1000005],a[1000005];
long long S[1000005]={0};
int lowbit(int x)
{
	return x&(-x);
}
void update(int i,int x)
{
	while(i<=n)S[i]+=x,i+=lowbit(i);
}
long long getsum(int i)
{
	long long s=0;
	while(i)s+=S[i],i-=lowbit(i);
	return s; 
}
vector<int>R[1000005];
void DFS(int x,int fa)
{
	int i,j;
	in[x]=++tot,update(tot,a[x]);
	for(i=0;i<R[x].size();i++)
	{
		j=R[x][i];
		if(j!=fa)DFS(j,x);
	}
	out[x]=tot;
}
int main()
{
	int i,x,y,op;
	scanf("%d%d%d",&n,&m,&k);
	for(i=1;i<=n;i++)scanf("%d",&a[i]);
	for(i=0;i<n-1;i++)
	{
		scanf("%d%d",&x,&y);
		R[x].push_back(y),R[y].push_back(x);
	}
	DFS(k,0);
	while(m--)
	{
		scanf("%d%d",&op,&x);
		if(op==1)scanf("%d",&y),update(in[x],y);
		else printf("%lld\n",getsum(out[x])-getsum(in[x]-1));
	}
    return 0;
}

C++14(g++5.4) 解法, 执行用时: 1500ms, 内存消耗: 112516K, 提交时间: 2020-04-19 11:28:40

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+5;
int tr[N],n,m,k,a[N],in[N],out[N],tot;
typedef long long ll;
#define lowbit(x) (x&-x)
vector<int>e[N];
void upd(int i,int x){
	while(i<=n){
		tr[i]+=x;
		i+=lowbit(i);
	}
}
ll sum(int i){
	ll sum=0;
	while(i) sum+=tr[i],i-=lowbit(i);
	return sum;
}
void dfs(int u,int fa){
	in[u]=++tot,upd(tot,a[u]);
	for(auto v:e[u]){
		if(v!=fa) dfs(v,u);
	}
	out[u]=tot;
}
int main(){
	scanf("%d%d%d",&n,&m,&k);
	for(int i=1;i<=n;i++) scanf("%d",&a[i]);
	for(int i=1,u,v;i<n;i++){
		scanf("%d%d",&u,&v);
		e[u].push_back(v),e[v].push_back(u);
	}
	dfs(k,0);
	while(m--){
		int op,a,x;
		scanf("%d%d",&op,&a);
		if(op==1) scanf("%d",&x),upd(in[a],x);
		else printf("%lld\n",sum(out[a])-sum(in[a]-1));
	}
	return 0;
}