RE 60 分求条玄关

#include <bits/stdc++.h>
#define int long long
const int N = 800005;
const int X = 800000;
const int M = 5005;
using namespace std;
int n,m,ll[N],rr[N],ls,maxn,rt[N],x,y,z,father[N][35],dep[N],cnt,tag[N],ans[N],ans2[N];
vector<int> vec[N];
void BL(int root,int L,int R){
	if(L == R){
		if(maxn == tag[root])
			ans[ls] = min(ans[ls],L);
		else if(maxn < tag[root]){
			maxn = tag[root];
			ans[ls] = L;
		}
		return ;
	}
	int mid = (L + R) >> 1;
	if(ll[root])
		BL(ll[root],L,mid);
	if(rr[root])
		BL(rr[root],mid+1,R);
	return;
}
void dfs(int v,int f){
	dep[v] = dep[f] + 1;
	father[v][0] = f;
	for(int i = 1;i <= 30;i++)
		father[v][i] = father[father[v][i-1]][i-1];
	for(int i = 0;i < vec[v].size();i++)
		if(vec[v][i] != f)
			dfs(vec[v][i],v);
	return;
}
int LCA(int x,int y){
	if(dep[x] < dep[y])
		swap(x,y);
	for(int i = 30;i >= 0;i--)
		if(dep[father[x][i]] >= dep[y])
			x = father[x][i];
	if(x == y)
		return x;
	for(int i = 30;i >= 0;i--){
		if(father[x][i] != father[y][i]){
			x = father[x][i];
			y = father[y][i];
		}
	}
	return father[x][0];
}
void XG(int&root,int l,int r,int L,int R,int v){
	if(!root) root = ++cnt;
	if(L >= l && R <= r){
		tag[root] += v;
		return;
	}
	int mid = (L+R)>>1;
	if(mid >= l)
		XG(ll[root],l,r,L,mid,v);
	if(mid < r)
		XG(rr[root],l,r,mid+1,R,v);
	return;
}
pair<int,int> query(int id,int l,int r){
	if(id == 0)
		return {0,0};
	if(l == r)
		return {l,tag[id]};
	int mid = (l + r) >> 1;
	pair<int,int> L = query(ll[id],l,mid),R = query(rr[id],mid+1,r);
	if(L.second >= R.second)
		return L;
	else 
		return R;
}
int merge(int x,int y,int l,int r){
	if(!x || !y) return x+y;
	if(l == r){
		tag[x] += tag[y];
		return x;
	}
	int mid = (l+r)>>1;
	ll[x] = merge(ll[x],ll[y],l,mid);
	rr[x] = merge(rr[x],rr[y],mid+1,r);
	tag[x] = tag[ll[x]] + tag[rr[x]];
	return x;
}
void dfs2(int s,int f){
	int x = -1;
	for(int i = 0;i < vec[s].size();i++){
		int v = vec[s][i];
		if(v != f){
			dfs2(v,s);
			if(x == -1)
				x = rt[v];
			else
				x = merge(x,rt[v],1,X);
		}
	}
	if(x != -1){
		x = merge(rt[s],x,1,X);
		rt[s] = x;
		ls = s;maxn = -1;
		BL(x,1,X);
		if(maxn == 0)
			ans[s] = 0;
	}
	else{
		ls = s;maxn = -1;
		BL(rt[s],1,X);
	}
	return;
}
signed main(){
	memset(ans,0x3f3f3f3f,sizeof ans);
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin >> n >> m;
    for(int i = 1;i < n;i++){
    	cin >> x >> y;
    	vec[x].push_back(y);
    	vec[y].push_back(x);
	}
	dfs(1,0);
	for(int i = 1;i <= m;i++){
		cin >> x >> y >> z;
		int l = LCA(x,y);
		XG(rt[x],z,z,1,X,1);
		XG(rt[y],z,z,1,X,1);
		XG(rt[l],z,z,1,X,-1);
		XG(rt[father[l][0]],z,z,1,X,-1);
	}
	dfs2(1,0);
	for(int i = 1;i <= n;i++){
		if(ans[i] == 4557430888798830399)
			cout << 0 << '\n';
		else
			cout << ans[i] << '\n';
	}
	return 0;
}