#include #include #include #include #include using namespace std; struct disjoint_set { vector p; disjoint_set(int n) { p.assign(n, -1); } int find(int x) { if (p[x] < 0) return x; return p[x] = find(p[x]); } bool merge(int x, int y) { x = find(x); y = find(y); if(x == y) return false; p[x] = y; return true; } }; struct node { node *nxt; node *end; int val; node(node* a, node* b, int c) { nxt=a; end=b; val=c; } }; int main() { int n; cin >> n; vector> actualvalues(n+1); // vector par(n+1); vector done(n+1); vector> children(n+1); done[0] = true; for(int i = 1; i <= n; i++) { cin >> actualvalues[i][1] >> actualvalues[i][2] >> par[i]; children[par[i]].push_back(i); actualvalues[i][3] = i; actualvalues[i][0] = actualvalues[i][1] / (1 - actualvalues[i][2]); } vector> donatedvalues = actualvalues; // priority_queue, vector>, greater>> q; for(int i = 1; i <= n; i++) { q.push(actualvalues[i]); } vector ret; int amt = 0; vector donated(n+1); disjoint_set dsu(n+1); vector nodes(n+1); for(int i = 1; i <= n; i++) { nodes[i] = new node(NULL, NULL, i); nodes[i]->end = nodes[i]; } while(q.size()) { auto [ec, c, p, idx] = q.top(); q.pop(); if(done[idx]) continue; done[idx] = true; int id = dsu.find(par[idx]); if(par[idx] == 0 || done[id]) { node* curr = nodes[idx]; while(curr) { done[curr->val] = true; ret.push_back(curr->val); curr = curr->nxt; } continue; } dsu.merge(idx, par[idx]); int upd = dsu.find(idx); donatedvalues[upd][1] += donatedvalues[upd][2] * donatedvalues[idx][1]; donatedvalues[upd][2] *= donatedvalues[idx][2]; donatedvalues[upd][0] = donatedvalues[upd][1] / (1 - donatedvalues[upd][2]); nodes[upd]->end->nxt = nodes[idx]; nodes[upd]->end = nodes[idx]->end; q.push(donatedvalues[upd]); } for(int out: ret) cout << out << "\n"; }