AtCoder Beginner Contest 187E

ABC190E

Tree におけるクエリ． まとめて処理することで回数を減らす，いつものやつ．

Subtree に関する処理を，補題の様に扱えばよい． Subtree の root \(r\) を指定したとき，\(r\) の値を subtree 全体に伝搬させる．

使っている記号，マクロ等 "https://ecsmtlir.hatenablog.com/entry/2022/12/23/131925"

int main() {

  ll n;

  cin >> n;

  vvll to(n);

  vector<pll> ed(n-1);

  rep(i,n-1){

    ll a,b; cin >> a >> b;

    --a, --b;

    to[a].push_back(b);

    to[b].push_back(a);

    ed[i] = {a,b};

  }

  ll q; cin >> q;

  vll val(n), dep(n);

  auto dfs = [&](auto dfs, ll cu, ll pa = -1, ll d = 0) -> void {

    dep[cu] = d;

    for(auto ne: to[cu]) if(ne != pa){

      val[ne] += val[cu];

      dfs(dfs, ne, cu, d+1);

    }

  };

  // depth を求める

  dfs(dfs,0); // val は全て 0 なので，valは変更されない

 

  // Remark: クエリを処理する時点では，すでに depth が求まっている前提

  // クエリ先読みをするか，先に depth を求めるか．

  rep(qi,q){

    ll t,e,x; cin >> t >> e >> x;

    e--;

    auto [a,b] = ed[e];

    if(t == 2) swap(a,b);

    if(dep[a] > dep[b]){

      val[a] += x;

    }else{

      val[0] += x;

      val[b] -= x;

    }

  }

 

  // val を求める

  dfs(dfs, 0);

 

  rep(i,n){

    cout << val[i] << endl;

  }

 

  return 0;

}