Codeforces
CF Step
Youtube Linkedin Discord Toggle Dark/Light/Auto mode Toggle Dark/Light/Auto mode Toggle Dark/Light/Auto mode Back to homepage

Code : Subtree Sum

#include <bits/stdc++.h>
using namespace std;

class Tree {
  public:
    int n, timer;
    vector<vector<int>> adj;
    vector<int> tin, tout;
    vector<long long> a, event;

    Tree(int n) {
        this->n = n;
        adj.resize(n);
        tin.resize(n);
        tout.resize(n);
        a.resize(n);
        event.resize(2 * n + 1);
        timer = 0;
    }

  public:
    void dfs(int src, int par) {
        tin[src] = ++timer;
        event[tin[src]] = a[src];
        for (auto child : adj[src]) {
            if (child != par) {
                dfs(child, src);
            }
        }
        tout[src] = ++timer;
        event[tout[src]] = 0;
    }
};

void solve() {
    int n;
    cin >> n;
    Tree t(n);
    for (int i = 0; i < n; i++) {
        cin >> t.a[i];
    }
    for (int i = 0; i < n - 1; i++) {
        int x, y;
        cin >> x >> y;
        x--;
        y--;
        t.adj[x].push_back(y);
        t.adj[y].push_back(x);
    }
    t.dfs(0, -1);

    for (int i = 0; i < n; i++) {
        long long sum = 0;
        for (int x = t.tin[i]; x <= t.tout[i]; x++) {
            sum += t.event[x];
        }
        cout << sum << " ";
    }
    cout << endl;
}

int main() {
    int t;
    cin >> t;
    for (int zz = 0; zz < t; zz++) {
        solve();
    }
    return 0;
}
#include <bits/stdc++.h>
using namespace std;

long long query(vector<long long> &pref, int l, int r) {
    return pref[r] - (l ? pref[l - 1] : 0);
}

class Tree {
  public:
    int n, timer;
    vector<vector<int>> adj;
    vector<int> tin, tout;
    vector<long long> a, event;

    Tree(int n) {
        this->n = n;
        adj.resize(n);
        tin.resize(n);
        tout.resize(n);
        a.resize(n);
        event.resize(2 * n + 1);
        timer = 0;
    }

  public:
    void dfs(int src, int par) {
        tin[src] = ++timer;
        event[tin[src]] = a[src];
        for (auto child : adj[src]) {
            if (child != par) {
                dfs(child, src);
            }
        }
        tout[src] = ++timer;
        event[tout[src]] = 0;
    }
};

void solve() {
    int n;
    cin >> n;
    Tree t(n);
    for (int i = 0; i < n; i++) {
        cin >> t.a[i];
    }
    for (int i = 0; i < n - 1; i++) {
        int x, y;
        cin >> x >> y;
        x--;
        y--;
        t.adj[x].push_back(y);
        t.adj[y].push_back(x);
    }
    t.dfs(0, -1);

    for (int i = 1; i <= 2 * n; i++) {
        t.event[i] += t.event[i - 1];
    }

    for (int i = 0; i < n; i++) {
        long long sum = 0;
        sum = query(t.event, t.tin[i], t.tout[i]);
        cout << sum << " ";
    }
    cout << endl;
}

int main() {
    int t;
    cin >> t;
    for (int zz = 0; zz < t; zz++) {
        solve();
    }
    return 0;
}
#include <bits/stdc++.h>
using namespace std;

class Tree {
  public:
    int n, timer;
    vector<vector<int>> adj;
    vector<long long> a, dp;

    Tree(int n) {
        this->n = n;
        adj.resize(n);
        a.resize(n);
        dp.resize(n);
        timer = 0;
    }

  public:
    void dfs(int src, int par) {
        dp[src] = a[src];
        for (auto child : adj[src]) {
            if (child != par) {
                dfs(child, src);
                dp[src] += dp[child];
            }
        }
    }
};

void solve() {
    int n;
    cin >> n;
    Tree t(n);
    for (int i = 0; i < n; i++) {
        cin >> t.a[i];
    }
    for (int i = 0; i < n - 1; i++) {
        int x, y;
        cin >> x >> y;
        x--;
        y--;
        t.adj[x].push_back(y);
        t.adj[y].push_back(x);
    }
    t.dfs(0, -1);

    for (int i = 0; i < n; i++) {
        cout << t.dp[i] << " ";
    }
    cout << endl;
}

int main() {
    int t;
    cin >> t;
    for (int zz = 0; zz < t; zz++) {
        solve();
    }
    return 0;
}