#include<bits/stdc++.h> #define ll long long #define pii pair<int,int> #define fi first #define se second #define mk make_pair using namespace std; const int N=2e5+10; vector<int> E[N]; int a[N],d[N],k[N]; int n; namespace BF{ ll res=0;int ac=0; void dfs(int u,int fa,ll val){ if(a[u]>=ac&&val<=k[u]){ res+=a[u]; }if(val>k[u]) return ; val+=d[u]; for(auto v:E[u]){ if(v==fa) continue; dfs(v,u,val); } }void slv(){ for(int i=1;i<=n;i++){ res=0;ac=a[i]; dfs(i,0,0); cout<<res<<' '; }cout<<endl; } } struct bit{ ll T[N];vector<pair<int,ll>> opt; int lb(int x){return x&(-x);} void upd(int x,ll v,bool op=1){ if(op) opt.push_back(mk(x,v)); for(int i=x;i<=n;i+=lb(i)) T[i]+=v; }ll qry(int x){ ll res=0; for(int i=x;i>0;i-=lb(i)) res+=T[i]; return res; }void clr(){ //memset(T,0,sizeof(T)); for(auto ed:opt) upd(ed.fi,-ed.se,0); opt.clear(); } }b; int siz[N]; ll sumd[N],lim[N]; ll ans[N]; map<int,int> mp; bool vis[N]; void ginfo(int u,int fa,int rt){ lim[u]=min(lim[fa],k[u]-sumd[fa]); if(lim[u]>=0&&a[u]>=a[rt]) ans[rt]+=a[u]; sumd[u]=sumd[fa]+d[u];siz[u]=0; for(auto v:E[u]){ if(v==fa||vis[v]) continue; ginfo(v,u,rt);siz[u]+=siz[v]; }siz[u]++; } void getz(int u,int fa,int all,pii &node){ int mxs=all-siz[u]; for(auto v:E[u]){ if(v==fa||vis[v]) continue; getz(v,u,all,node); mxs=max(mxs,siz[v]); }node=min(node,mk(mxs,u)); } vector<int> ap; vector<pii> upd,qry;//id-lm void solve2d(int op){ auto cmp=[](pii a,pii b){ return a.se<b.se; }; sort(upd.begin(),upd.end(),cmp); sort(qry.begin(),qry.end(),cmp); reverse(qry.begin(),qry.end()); for(auto ed:qry){ //cout<<ed.fi<<' '<<ed.se<<endl; while(!upd.empty()){ if(upd.back().se>=ed.se){ int id=upd.back().fi;//cout<<a[id]<<' '; b.upd(a[id],a[id]);upd.pop_back(); }else{ break; } }ll res=b.qry(n)-b.qry(a[ed.fi]-1);//cout<<endl; ans[ed.fi]+=res*op;//cout<<ed.fi<<' '; }//cout<<endl; b.clr();upd.clear();qry.clear(); } void addinfo(int u,int fa,ll sum,ll lm){ sum+=d[u];lm=min(lm,k[u]+sumd[u]); if(sumd[u]<=lm) qry.push_back(mk(u,sum)); upd.push_back(mk(u,lim[u])); for(auto v:E[u]){ if(v==fa||vis[v]) continue; addinfo(v,u,sum,lm); } } void divide(int u){ //cout<<u<<endl; vis[u]=1;sumd[u]=d[u];lim[u]=k[u]; for(auto v:E[u]){ if(vis[v]) continue; ginfo(v,u,u); addinfo(v,u,0,k[u]+d[u]); }upd.push_back(mk(u,lim[u])); //for(auto ed:upd) cout<<ed.fi<<' '<<ed.se<<endl;cout<<endl; //(auto ed:qry) cout<<ed.fi<<' '<<ed.se<<endl; solve2d(1);//cout<<"divide: "<<u<<' '<<ans[3]<<endl; //for(int i=1;i<=n;i++) cout<<ans[i]<<' ';cout<<endl; //for(int i=1;i<=n;i++) cout<<lim[i]<<' ';cout<<endl<<endl; for(auto v:E[u]){ if(vis[v]) continue; addinfo(v,u,0,k[u]+d[u]);solve2d(-1); pii z=mk(1e9,0); getz(v,u,siz[v],z);divide(z.se); } } void slv(){ cin>>n; for(int i=1;i<=n;i++) cin>>a[i]>>d[i]>>k[i]; for(int i=1;i<=n;i++) E[i].clear(); for(int i=1;i<n;i++){ int u,v;cin>>u>>v; E[u].push_back(v); E[v].push_back(u); } //BF::slv(); for(int i=1;i<=n;i++) ans[i]=0,vis[i]=0; ginfo(1,0,0);pii z=mk(1e9,0); getz(1,0,siz[1],z);divide(z.se); for(int i=1;i<=n;i++) cout<<ans[i]+a[i]<<' ';cout<<endl; } int main(){ ios::sync_with_stdio(0);cin.tie(0);cout.tie(0); int sub,t;cin>>sub>>t; while(t--) slv(); cout.flush(); return 0; }