【題解】AtCoder 138D – Ki

題目敘述https://atcoder.jp/contests/abc138/tasks/abc138_d
解題想法:樹上DFS

  • 題目是一棵有根樹,有N個節點,N-1條邊。根節點編號為 1。
  • 由範測得知,測資可能對一個節點進行多次操作。因此,讀入測資時,順便統計外加在每個節點上的時間。
  • 從根節點開始DFS,遍歷每個節點,同時把每個節點上的timer時間,加到其子樹的所有節點上。
#include <iostream>
#include <vector>
using namespace std;
#define maxn 200005
vector<int> G[maxn];
long long timer[maxn];
long long ans[maxn];

void dfs(int now, int pre, int Time){
    Time += timer[now];
    ans[now] = Time;
    for (auto nxt: G[now]){
        if (nxt == pre) continue;
        dfs(nxt, now, Time);
    }
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int N, Q, a, b, p, x;
    cin >> N >> Q;
    for (int i=1; i<=N-1; i++){
        cin >> a >> b;
        G[a].push_back(b);
        G[b].push_back(a);
    }
    while (Q--){
        cin >> p >> x;
        timer[p] += x;
    }
    dfs(1, 0, 0);
    for (int i=1; i<=N; i++){
        cout << ans[i] << ' ';
    }
    cout << '\n';
    return 0;
}

分享本文 Share with friends