#include <bits/stdc++.h> using namespace std; #define int long long #define endl "\n" int n; int a[200300],d[200300],k[200300],PANS[200300]; vector<int>g[200300]; int siz[200300],mx[200300],rt; int ANS[200300]; bool vis[200300]; inline void clr(){ mx[0]=1e9; for(int i=1;i<=n;i++) g[i].clear(),siz[i]=mx[i]=0,vis[i]=0,ANS[i]=0,PANS[i]=0; } inline void dfssz(int u,int fa){ siz[u]=1; for(int v:g[u]) if(v!=fa&&!vis[v])dfssz(v,u),siz[u]+=siz[v]; } inline void dfsrt(int u,int fa,int S){ mx[u]=0; for(int v:g[u]) if(v!=fa&&!vis[v]){ dfsrt(v,u,S); mx[u]=max(mx[u],siz[v]); } mx[u]=max(mx[u],S-siz[u]); if(mx[u]<mx[rt])rt=u; } int t[200300]; inline int lb(int x){return x&-x;} inline void mod(int x,int k){while(x)t[x]+=k,x-=lb(x);} inline int gt(int x){ int res=0; while(x<=n)res+=t[x],x+=lb(x); return res; } inline void clr(int x){while(x)t[x]=0,x-=lb(x);} struct node{ int x,y,id; }; inline bool cmp(node A,node B){ return A.x==B.x?A.y==B.y?A.id<B.id:A.y>B.y:A.x>B.x; } inline void calc(vector<node>T,int k){ sort(T.begin(),T.end(),cmp); for(node A:T){ //cout<<A.x<<"x"<<A.y<<"x"<<A.id<<"x"<<gt(A.y)<<endl; if(!A.id) mod(A.y,k*A.y); else ANS[A.id]+=gt(A.y); } for(node A:T) if(!A.id)clr(A.y); // for(int i=1;i<=n;i++) // cout<<ANS[i]<<" "; // cout<<endl<<endl; } inline void ins(int u,int fa,vector<node>&T,int limtu,int limtd,int c,int rt,bool ok){ limtd=min(limtd,k[u]-c); c+=d[u]; if(d[rt]<=limtd&&a[rt]<=a[u]) ANS[rt]+=a[u]; //cout<<u<<" "<<limtd<<" "<<a[u]<<" 0"<<endl; T.push_back({limtd,a[u],0}); limtu=min(limtu-d[u],k[u]); if(limtu<0)ok=0; if(ok&&c<=k[rt]) T.push_back({c+d[rt],a[u],u}); //cout<<u<<" "<<c<<" "<<a[u]<<" 1"<<endl; if(c<=k[rt]&&ok&&a[rt]>=a[u]) ANS[u]+=a[rt]; for(int v:g[u]) if(!vis[v]&&v!=fa) ins(v,u,T,limtu,limtd,c,rt,ok); } int cnt=0; inline void calc(int u){ vector<node>ALL; for(int v:g[u]) if(!vis[v]){ vector<node>S; ins(v,u,S,k[u],2e9,0,u,1); calc(S,-1); for(node x:S) ALL.push_back(x); } calc(ALL,1); } inline int fdrt(int u){ dfssz(u,0); rt=0; dfsrt(u,0,siz[u]); return rt; } inline void dfs(int u){ vis[u]=1; calc(u); cnt++; for(int v:g[u]) if(!vis[v]) dfs(fdrt(v)); } inline void Fdfs(int u,int fa,int l,int s){ s+=d[u]; if(a[u]>=a[l]) PANS[l]+=a[u]; for(int v:g[u]) if(v!=fa&&s<=k[v]) Fdfs(v,u,l,s); } signed main(){ ios::sync_with_stdio(); freopen("wicked.in","r",stdin); freopen("wicked.out","w",stdout); mx[0]=1e9; int id,t; cin>>id>>t; while(t--){ cnt=0; cin>>n; for(int i=1;i<=n;i++) cin>>a[i]>>d[i]>>k[i]; for(int i=1;i<n;i++){ int u,v; cin>>u>>v; g[u].push_back(v); g[v].push_back(u); } // for(int i=1;i<=n;i++) // Fdfs(i,0,i,0); dfs(fdrt(1)); for(int i=1;i<=n;i++) ANS[i]+=a[i]; for(int i=1;i<=n;i++) cout<<ANS[i]<<" "; cout<<endl; // for(int i=1;i<=n;i++) // cout<<PANS[i]<<" "; // cout<<endl; // // for(int i=1;i<=n;i++) // if(ANS[i]!=PANS[i]){ // for(int i=1;i<=n;i++) // cout<<a[i]<<" "<<d[i]<<" "<<k[i]<<endl; // for(int i=1;i<=n;i++) // for(int j:g[i]) // if(j<i) // cout<<j<<" "<<i<<endl;exit(0); // } clr(); } cout.flush(); return 0; } /* 1 1 3 3 2 3 1 1 2 3 2 3 1 2 2 3 */