G_Path_Prefixes.cpp

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

const int N = 2e5 + 5;
vector<array<int, 3>> adj[N];
int dp[N];
vector<int> temp;

void dfs(int node, int sum, int sum2) {
    dp[node] = upper_bound(temp.begin(), temp.end(), sum) - temp.begin();
    for(auto &[ch, ai, bi] : adj[node]) {
        temp.push_back(sum2 + bi);
        dfs(ch, sum + ai, sum2 + bi);
        temp.pop_back();
    }
}

void YHTWH() {
    int n;
    cin >> n;
    for(int i=0;i<=n;i++) {
        adj[i].clear();
        dp[i] = 0;
    }
    temp.clear();

    for(int i=2;i<=n;i++) {
        int p, a, b;
        cin >> p >> a >> b;
        adj[p].push_back({i, a, b});
    }

    dfs(1, 0, 0);

    for(int i=2;i<=n;i++) cout << dp[i] << " "; cout << "\n";

}


int32_t main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    int _;
    cin >> _;
    while (_-->0) {
        YHTWH();
    }

    return 0;
}