[AtCoder] ABC 138 D – Ki

2019年8月19日

問題

方針

幅優先探索

頂点 \( 1 \) から幅優先探索を行って全ての頂点のカウンターの値を計算します。そのために、頂点 \( i \) が最初のカウンターの値をあらかじめ計算します。最初のカウンターの値とは、ある頂点 \( u \) が \( u = p_i \ (1 \leq i \leq N)\) を満たすような頂点 \( u \) に \( x_i \) を加算した値です。ここで、頂点 \( i \) のカウンターの値を \( c_i \) とします。

頂点 \( 1 \) を親として、子のカウンターの値に \( c_1 \) を加算するというように、親から子に向かってカウンターの値を加算していきます。この探索では、隣接リストとキューを用いて幅優先探索を行うことができます。

コード

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main() {
  int N, Q;
  cin >> N >> Q;
  int a[N - 1], b[N - 1];
  // 隣接リスト
  vector<int> adj[N];
  for (int i = 0; i < N - 1; i++) {
    cin >> a[i] >> b[i];
    a[i]--;
    b[i]--;
    adj[a[i]].push_back(b[i]);
    adj[b[i]].push_back(a[i]);
  }
  int p[Q];
  ll x[Q];
  ll c[N]{};
  for (int i = 0; i < Q; i++) {
    cin >> p[i] >> x[i];
    p[i]--;
    c[p[i]] += x[i];
  }
  ll t = 0;
  deque<int> q;
  q.push_back(0);
  int vis[N]{};
  vis[0] = 1;
  while(!q.empty()) {
    int u = q.front();
    q.pop_front();
    for (int i : adj[u]) {
      if (vis[i] == 1) continue;
      vis[i] = 1; 
      c[i] += c[u];
      q.push_back(i);
    }
  }
  for (int i = 0; i < N; i++) {
    if (i == N - 1) {
      cout << c[i] << "\n";
    } else {
      cout << c[i] << " ";
    }
  }
  return 0;
}