Code : Iris and the Tree

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

#define node first
#define index second

class Tree {
  public:
    int n;
    vector<vector<int>> adj;
    vector<int> parent;
    vector<int> free_edges;
    vector<int> mx;
    vector<long long> assigned;
    Tree(int n) {
        this->n = n;
        adj.resize(n);
        parent.resize(n, -1);
        mx.resize(n);
        free_edges.resize(n);
        assigned.resize(n);
    }

    void dfs(int src) {
        mx[src] = src;
        for (auto child : adj[src]) {
            dfs(child);
            mx[src] = max(mx[src], mx[child]);
        }
    }

    void add_free_edge(int p, int c) {
        int prev = (c - 1 + n) % n;
        for (int v : {prev, mx[c]}) {
            free_edges[v]++;
        }
    }

    void remove_free_edge(int p, int c, long long w) {
        int prev = (c - 1 + n) % n;
        for (int v : {prev, mx[c]}) {
            free_edges[v]--;
            assigned[v] += w;
        }
    }

    void reveal(long long remain) {
        for (int c = 1; c < n; c++) {
            add_free_edge(parent[c], c);
        }

        int cnt = n - 1;
        while (cnt--) {
            int x;
            long long y;
            cin >> x >> y;
            x--;
            remain -= y;
            remove_free_edge(parent[x], x, y);
            long long ans = 0;
            for (int i = 0; i < n; i++) {
                ans += assigned[i];
                if (free_edges[i]) {
                    ans += remain;
                }
            }
            cout << ans << " ";
        }
        cout << endl;
    }
};

void solve() {
    int n;
    long long total;
    cin >> n >> total;

    Tree t(n);
    for (int i = 1; i < n; i++) {
        cin >> t.parent[i];
        t.parent[i]--;
        t.adj[t.parent[i]].push_back(i);
    }

    t.dfs(0);
    t.reveal(total);
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int t;
    cin >> t;
    while (t--) {
        solve();
    }
}

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

#define node first
#define index second

class Tree {
  public:
    int n;
    vector<vector<int>> adj;
    vector<int> parent;
    vector<int> free_edges;
    vector<int> mx;
    vector<long long> assigned;
    int unlocked_count;
    long long locked_sum, unlocked_sum;
    Tree(int n) {
        this->n = n;
        adj.resize(n);
        parent.resize(n, -1);
        mx.resize(n);
        free_edges.resize(n);
        assigned.resize(n);
    }

    void dfs(int src) {
        mx[src] = src;
        for (auto child : adj[src]) {
            dfs(child);
            mx[src] = max(mx[src], mx[child]);
        }
    }

    void add_free_edge(int p, int c) {
        int prev = (c - 1 + n) % n;
        for (int v : {prev, mx[c]}) {
            free_edges[v]++;
        }
    }

    void remove_free_edge(int p, int c, long long w) {
        int prev = (c - 1 + n) % n;
        for (int v : {prev, mx[c]}) {
            free_edges[v]--;
            assigned[v] += w;
            unlocked_sum += w;
            if (free_edges[v] == 0) {
                unlocked_count--;
                locked_sum += assigned[v];
                unlocked_sum -= assigned[v];
            }
        }
    }

    void reveal(long long remain) {
        for (int c = 1; c < n; c++) {
            add_free_edge(parent[c], c);
        }

        unlocked_count = n, locked_sum = 0, unlocked_sum = 0;

        int cnt = n - 1;
        while (cnt--) {
            int x;
            long long y;
            cin >> x >> y;
            x--;
            remain -= y;
            remove_free_edge(parent[x], x, y);
            long long ans = locked_sum + unlocked_sum + unlocked_count * remain;
            cout << ans << " ";
        }
        cout << endl;
    }
};

void solve() {
    int n;
    long long total;
    cin >> n >> total;

    Tree t(n);
    for (int i = 1; i < n; i++) {
        cin >> t.parent[i];
        t.parent[i]--;
        t.adj[t.parent[i]].push_back(i);
    }

    t.dfs(0);
    t.reveal(total);
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int t;
    cin >> t;
    while (t--) {
        solve();
    }
}