根から辿る全探索

木上の累積和で、根から足しこむところで詰まっていたので、そこ含めてメモとして記録。

memo

void dfs(int thisNode, int parent, vector<vector<int>>& graph, vector<int>& c) {
    for (auto nextNode : graph[thisNode]) {
        if (nextNode == parent) {
            continue;
        }
        c[nextNode] += c[thisNode];
        dfs(nextNode, thisNode, graph, c);
    }
}

int main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);

    int n, q;
    cin >> n >> q;
    vector<vector<int>> graph(n, vector<int>());

    for (size_t i = 0; i < n - 1; i++)
    {
        int a, b;
        cin >> a >> b;
        a--; b--; // 0 indexed
        graph[a].emplace_back(b);
        graph[b].emplace_back(a);
    }

    vector<int> c(n, 0);
    for (size_t i = 0; i < q; i++)
    {
        int p, x;
        cin >> p >> x;
        p--; // 0 indexed

        c[p] += x;
    }

    // 根から足しこむ
    dfs(0, -1, graph, c);

    for (auto result : c) {
        cout << result << " ";
    }
    return 0;
}