记录编号	463612	评测结果	AAAATTTTTT
题目名称	2551.新型武器	最终得分	40
用户昵称	coolkid	是否通过	未通过
代码语言	C++	运行时间	6.045 s
提交时间	2017-10-24 15:23:49	内存使用	4.89 MiB

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#include<queue>
using namespace std;

const int MAXN=300010;

vector<int> sn[MAXN];
int w[MAXN];

void query(int u,int c){
	int ans=0;
	queue< pair<int,int> > q;
	q.push(make_pair(u,0));
	while(!q.empty()){
		pair<int,int> x=q.front();q.pop();
		if(x.second==c){
			ans+=w[x.first];
		}
		else if(x.second<c) {
			for(int i=0;i<sn[x.first].size();i++) q.push(make_pair(sn[x.first][i],x.second+1));
		} 
	}
	cout<<ans<<endl;
}

int main(){
	freopen("newweapon.in","r",stdin);
	freopen("newweapon.out","w",stdout);
	int n;
	ios::sync_with_stdio(false);
	cin>>n;
	for(int i=1;i<=n;i++) cin>>w[i];
	for(int i=1;i<n;i++){
		int fr,to;
		cin>>fr>>to;
		sn[fr].push_back(to);
	}
	
	int Q;
	cin>>Q;
	for(int i=1;i<=Q;i++){
		int opt,u,v;
		cin>>opt>>u>>v;
		if(opt==2) query(u,v);
		else  w[u]=v;
	}
	return 0;
}