D - Ki

・問題URL

https://atcoder.jp/contests/abc138/tasks/abc138_d

・発想

・youtubeのBFSゆっくり解説でみた問題。
・愚直にシミュレーションをするとO(NQ)でアウト。

・解法

・まず入力の分だけカウントして１から追っていき、親のカウンターの数を足していっても同じ。これはO(N)ゆえ、BFS,DFSだとO(N+Q)で解ける。

・コード

・BFS.ver

int main(){
 
 int N,Q;
 cin>>N>>Q;
 Graph G(N);
 vector<ll>count(N);
 rep(i,N-1){
   int a,b;
   cin>>a>>b;
   G[a-1].push_back(b-1);
   G[b-1].push_back(a-1);
 }
 rep(i,Q){
   int a,b;
   cin>>a>>b;
   count[a-1]+=b;
 }
 
 queue<int>que;
 vector<bool>seen(N,false);
 que.push(0);
 seen[0]=true;
 while (!que.empty()){
  int v=que.front();
  que.pop();
  for(auto nv:G[v]){
    if(seen[nv])continue;
    seen[nv]=true;
    count[nv]+=count[v];
    que.push(nv);
  }

 }
 
rep(i,N)cout<<count[i]<<" ";
 
}

・DFS.ver(なぜか変数countをmain関数の外で宣言したらCEしたので名前をAに変更）

vector<bool>seen;
vector<int>A;
void dfs(const Graph &G,int v){
 seen[v]=true;
 for(auto nv:G[v]){
   if(seen[nv])continue;
   A[nv]+=A[v];
   dfs(G,nv);
 }
}

int main(){


 int N,Q;
 cin>>N>>Q;
 Graph G(N);
 rep(i,N-1){
   int a,b;
   cin>>a>>b;
   G[a-1].push_back(b-1);
   G[b-1].push_back(a-1);
 }
 
 A.resize(N);
 rep(i,Q){
   int a,b;
   cin>>a>>b;
   A[a-1]+=b;
 }
 
 seen.resize(N);
 dfs(G,0);
 
 rep(i,N)cout<<A[i]<<" ";
 
}