#include<bits/stdc++.h> using namespace std; #define int long long #define lson p[now].son[0] #define rson p[now].son[1] #define pii pair<int,int> #define mp make_pair const int MAXN=500010,ie18=1000000000000000000; int _,__,n,m,a[MAXN],d[MAXN],k[MAXN]; struct Edge{int v,nx;}edge[MAXN<<1];int h[MAXN],CNT;void init(){for(int i=1;i<=n+10;i++)h[i]=-1;CNT=0;} void add_side(int u,int v){edge[++CNT]={v,h[u]};h[u]=CNT;edge[++CNT]={u,h[v]};h[v]=CNT;} bool vis[MAXN]; int get_sz(int now,int lst){ if(vis[now])return 0; int rt=1; for(int i=h[now];i!=-1;i=edge[i].nx){ if(edge[i].v!=lst)rt+=get_sz(edge[i].v,now); } return rt; } int sz,Zx,zsdx; int qzx(int now,int lst){ if(vis[now])return 0; int rt=0,sum=0,mx=0; for(int i=h[now];i!=-1;i=edge[i].nx){ if(edge[i].v!=lst){ int tmp=qzx(edge[i].v,now); sum+=tmp;mx=max(mx,tmp); } } mx=max(mx,sz-sum-1); if(mx<zsdx){ Zx=now; zsdx=mx; } return sum+1; } int cnts,cntt,zs_now; struct point{ int id,a,s,zs; bool operator <(const point&G)const{ return (s!=G.s)?s<G.s:a<G.a; } bool operator ==(const point&G)const{ return a==G.a&&s==G.s; } }s[MAXN],t[MAXN]; bool cmp(point x,point y){ return !(x<y); } bool cmp1(point x,point y){ return x.zs!=y.zs?x.zs<y.zs:!(x<y); } bool cmp2(point x,point y){ return x.zs!=y.zs?x.zs<y.zs:x<y; } void get_s(int now,int lst,int sum,int lmt){ if(vis[now])return; if(lmt-sum<0)return; // cout<<now<<" "<<sum<<" "<<lmt<<" "<<a[now]<<endl; s[++cnts]={now,a[now],sum,zs_now}; for(int i=h[now];i!=-1;i=edge[i].nx){ if(edge[i].v!=lst){ get_s(edge[i].v,now,sum+d[edge[i].v],min(k[now]+sum,lmt)); } } } void get_t(int now,int lst,int sum,int lmt){ if(vis[now])return; if(k[now]<sum)return; lmt=min(lmt,k[now]-sum); //cout<<now<<" "<<lst<<" "<<sum<<" "<<lmt<<endl; t[++cntt]={now,a[now],lmt,zs_now}; for(int i=h[now];i!=-1;i=edge[i].nx){ if(edge[i].v!=lst){ get_t(edge[i].v,now,sum+d[now],lmt); } } } int C[MAXN],ans[MAXN]; int lb(int x){return x&(-x);} int query(int x){int rt=0;for(int i=x;i>=1;i-=lb(i))rt+=C[i];return rt;} void update(int x,int y){for(int i=x;i<=n;i+=lb(i))C[i]+=y;} void dfz(int now,int lst){ if(vis[now])return; sz=get_sz(now,lst);zsdx=ie18;Zx=0; int tmp=qzx(now,lst);int zx=Zx; vis[zx]=1; cnts=zs_now=cntt=0; //cout<<now<<" "<<lst<<" "<<zx<<endl; for(int i=h[zx];i!=-1;i=edge[i].nx){ if(!vis[edge[i].v]){ zs_now++; get_s(edge[i].v,zx,d[edge[i].v],k[zx]); get_t(edge[i].v,zx,d[zx],k[zx]); } } s[++cnts]={zx,a[zx],0,zs_now+1}; t[++cntt]={zx,a[zx],k[zx],zs_now+2}; sort(s+1,s+cnts+1,cmp); sort(t+1,t+cntt+1,cmp);/* cout<<now<<" "<<lst<<endl; cout<<"S:"<<cnts<<endl; for(int i=1;i<=cnts;i++){ cout<<s[i].id<<" "<<s[i].a<<" "<<s[i].s<<" "<<s[i].zs<<endl; } cout<<"T:"<<cntt<<endl; for(int i=1;i<=cntt;i++){ cout<<t[i].id<<" "<<t[i].a<<" "<<t[i].s<<" "<<t[i].zs<<endl; }*/ for(int i=1,j=1;j<=cnts;j++){ while(i<=cntt&&t[i].s>=s[j].s){ update(t[i].a,t[i].a);i++; } ans[s[j].id]+=query(n)-query(s[j].a-1); // cout<<s[j].id<<"+="<<query(n)<<"-"<<query(s[j].a-1)<<endl; } for(int i=1,j=1;j<=cnts;j++){ while(i<=cntt&&t[i].s>=s[j].s){ update(t[i].a,-t[i].a);i++; } } sort(s+1,s+cnts+1,cmp1); sort(t+1,t+cntt+1,cmp1);/* cout<<"S:"<<cnts<<endl; for(int i=1;i<=cnts;i++){ cout<<s[i].id<<" "<<s[i].a<<" "<<s[i].s<<" "<<s[i].zs<<endl; } cout<<"T:"<<cntt<<endl; for(int i=1;i<=cntt;i++){ cout<<t[i].id<<" "<<t[i].a<<" "<<t[i].s<<" "<<t[i].zs<<endl; }*/ for(int lc=1,rc=1,ld=1,rd=1;lc<=cnts&&ld<=cntt;lc=rc+1,ld=rd+1){ rc=lc;rd=ld; while(rc+1<=cnts&&s[rc+1].zs==s[lc].zs)rc++; while(rd+1<=cntt&&t[rd+1].zs==t[ld].zs)rd++; bool fl=0; // cout<<" "<<lc<<" "<<rc<<" "<<ld<<" "<<rd<<endl; while(s[lc].zs!=t[ld].zs){ if(s[lc].zs<t[ld].zs){ lc=rc+1;rc++; while(rc+1<=cnts&&s[rc+1].zs==s[lc].zs)rc++; } else{ ld=rd+1;rd++; while(rd+1<=cntt&&t[rd+1].zs==t[ld].zs)rd++; } if(rd>cntt||rc>cnts){ fl=1; break; } // cout<<lc<<" "<<rc<<" "<<ld<<" "<<rd<<endl; } if(fl)break; //cout<<lc<<" "<<rc<<" "<<ld<<" "<<rd<<" "<<query(n)<<endl; for(int i=ld,j=lc;j<=rc;j++){ while(i<=rd&&t[i].s>=s[j].s){ update(t[i].a,t[i].a);i++; } ans[s[j].id]-=query(n)-query(s[j].a-1); // cout<<s[j].id<<"-="<<query(n)<<"-"<<query(s[j].a-1)<<endl; } for(int i=ld,j=lc;j<=rc;j++){ while(i<=rd&&t[i].s>=s[j].s){ update(t[i].a,-t[i].a);i++; } } } for(int i=h[zx];i!=-1;i=edge[i].nx){ if(!vis[edge[i].v]){ dfz(edge[i].v,zx); } } } void slv(){ scanf("%lld",&n);init(); for(int i=1;i<=n;i++){ans[i]=0;C[i]=0;vis[i]=0; scanf("%lld%lld%lld",&a[i],&d[i],&k[i]); } for(int i=1;i<n;i++){ int u,v; scanf("%lld%lld",&u,&v); add_side(u,v); } dfz(1,-1); for(int i=1;i<=n;i++){ printf("%lld ",ans[i]); } printf("\n"); } signed main(){ scanf("%lld%lld",&__,&_); while(_--)slv(); return 0; }