云剪贴板 nyzx8dq6

#include<bits/stdc++.h>
#define x0 x_0
#define x1 x_1
#define y0 y_0
#define y1 y_1
#define yn y_n
#define j0 j_0
#define j1 j_1
#define jn j_n
#define k0 k_0
#define k1 k_1
#define d0 d_0
#define d1 d_1
#define LL long long
#define LD long double
#define Big __int128
#define STR string
#define US unsigned
#define ZPB push_back
#define ZPF push_front
#define PPB pop_back
#define PPF pop_front
#define next NXTNXT
#define UPB upper_bound
#define LWB lower_bound
#define mem(x,v) memset(x,v,sizeof(x))
using namespace std;
const int V=100000,mxN=100010;
int n,m,par[mxN][17],dep[mxN],Log[mxN],mx[mxN*80],ls[mxN*80],rs[mxN*80],root[mxN],hd[mxN],TO[mxN<<1],next[mxN<<1],ecnt;
int rew[mxN<<2],rhd[mxN],rnxt[mxN<<2],rcnt,idcnt,ans[mxN];
template<typename Name> Name ABS(Name x) {return (x>=0 ? x : -x);}
void dfs(int x,int fa){
	par[x][0]=fa,dep[x]=dep[fa]+1;
	for(int i=1;i<=16;++i) par[x][i]=par[par[x][i-1]][i-1];
	for(int i=hd[x];~i;i=next[i]){
		int u=TO[i];
		if(u==fa) continue;
		dfs(u,x);
	}
	return ;
}
int merge(int x,int y,int l,int r){
	if(!x || !y) return x|y;
	if(l==r) {mx[x]+=mx[y];return x;}
	int mid=(l+r)>>1;
	ls[x]=merge(ls[x],ls[y],l,mid),
	rs[x]=merge(rs[x],rs[y],mid+1,r),
	mx[x]=max(mx[ls[x]],mx[rs[x]]);
	return x;
}
void upd(int &x,int l,int r,int pos,int data){
	if(!x) x=++idcnt;
	if(l==r) {mx[x]+=data;return ;}
	int mid=(l+r)>>1;
	if(pos<=mid) upd(ls[x],l,mid,pos,data);
	else upd(rs[x],mid+1,r,pos,data);
	mx[x]=max(mx[ls[x]],mx[rs[x]]);
	return ; 
}
int qry(int x,int l,int r){
	if(l==r) return l;
	int mid=(l+r)>>1;
	if(mx[x]==mx[ls[x]]) return qry(ls[x],l,mid);
	return qry(rs[x],mid+1,r);
}
void dfs2(int x,int fa){
	for(int i=hd[x];~i;i=next[i]){
		int u=TO[i];
		if(u==fa) continue;
		dfs2(u,x),root[x]=merge(root[x],root[u],1,V);
	}
	for(int i=rhd[x];~i;i=rnxt[i]) upd(root[x],1,V,ABS(rew[i]),(rew[i]>=0 ? 1 : -1));
	if(mx[root[x]]) ans[x]=qry(root[x],1,V);
	return ;
}
int get_LCA(int u,int v){
	if(dep[u]<dep[v]) swap(u,v);
	int cha=dep[u]-dep[v];
	while(~Log[cha]) u=par[u][Log[cha]],cha-=(1<<Log[cha]);
	if(u==v) return u;
	for(int i=16;i>=0;--i)
		if(par[u][i]^par[v][i]) u=par[u][i],v=par[v][i];
	return par[u][0];
}
void zpb(int u,int v) {TO[++ecnt]=v,next[ecnt]=hd[u],hd[u]=ecnt;return ;}
void add(int u,int val) {rew[++rcnt]=val,rnxt[rcnt]=rhd[u],rhd[u]=rcnt;return ;}
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin>>n>>m,Log[0]=-1,mem(hd,-1),mem(rhd,-1);
	for(int i=1;i<mxN;++i) Log[i]=Log[i>>1]+1;
	for(int i=1;i<n;++i){
		int u,v;
		cin>>u>>v,zpb(u,v),zpb(v,u);
	}
	dfs(1,0);
	for(int i=1;i<=m;++i){
		int x,y,z,LCA;
		cin>>x>>y>>z,LCA=get_LCA(x,y),add(x,z),add(y,z),add(LCA,-z),add(par[LCA][0],-z);
	}
	dfs2(1,0);
	for(int i=1;i<=n;++i) cout<<ans[i]<<"\n";
	return 0;
}