P4556 全WA了 /kk

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>

using namespace std;

const int N=100010,L=20;

int f[N][L],d[N],q[N],root[N],ans[N];
int h[N],to[N<<1],ne[N<<1];
int X[N],Y[N],Z[N],val[N];
int T,n,m,tot,t,num,cnt;

struct Segment{
	int l,r,v,pos;
}tr[N*40];

inline void read(int &x){
	x=0;int f=1;char c=getchar();
	while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}
	while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=getchar();}
	x*=f;
}

inline void add(int u,int v){
	to[tot]=v,ne[tot]=h[u],h[u]=tot++;
}

void bfs(){
	int hh=0,tt=0;
	q[0]=1,d[1]=1;
	while(hh <= tt){
		int x=q[hh++];
		for(int i=h[x];~i;i=ne[i]){
			int y=to[i];
			if(d[y]) continue;
			d[y]=d[x]+1;
			f[y][0]=x;
			for(int j=1;j<=t;++j)
				f[y][j]=f[f[y][j-1]][j-1];
			q[++tt]=y;
		}
	}
}

int lca(int x,int y){
	if(d[x] > d[y]) swap(x,y);
	for(int i=t;i>=0;--i)
		if(d[f[y][i]] >= d[x]) y=f[y][i];

	if(x == y) return x;
	for(int i=t;i>=0;--i)
		if(f[x][i] != f[y][i]) x=f[x][i],y=f[y][i];
	return f[x][0];
}

inline void pushup(int &u){
	tr[u].v=max(tr[tr[u].l].v,tr[tr[u].r].v);
	tr[u].pos=tr[tr[u].l].v >= tr[tr[u].r].v ? tr[tr[u].l].pos : tr[tr[u].r].pos;
}

void insert(int &u,int l,int r,int v,int delta){
	if(l == r){
		tr[u].v+=v;
		tr[u].pos=tr[u].v?l:0;
		return;
	}
	int mid=(l+r)>>1;
	if(v <= mid){
	    if(!tr[u].l) tr[u].l=++num;
	    insert(tr[u].l,l,mid,v,delta);
	} 
	else {
	    if(!tr[u].r) tr[u].r=++num;
	    insert(tr[u].r,mid+1,r,v,delta);
	}
	pushup(u);
}

int merge(int p,int q,int l,int r){
	if(!q) return p;
	if(!p) return q;

	if(l == r){
		tr[p].v+=tr[q].v;
		tr[p].pos=tr[p].v?l:0;
		return p; 
	}
	int mid=(l+r)>>1;
	merge(tr[p].l,tr[q].l,l,mid);
	merge(tr[p].r,tr[q].r,mid+1,r);
	pushup(p);
	return p;
}

void dfs(int u){
	for(int i=h[u];~i;i=ne[i]){
		int v=to[i];
		if(d[v] <= d[u]) continue;
		dfs(v);
		root[u]=merge(root[u],root[v],1,cnt);
	}
	ans[u]=tr[root[u]].pos;
}

int main(){
	memset(h,-1,sizeof h);
	read(n),read(m);
	t=(int)(log(n)/log(2))+1;
	for(int i=1;i<n;++i){
		int x,y;
		read(x),read(y);
		add(x,y),add(y,x);
	}

	bfs();
	for(int i=1;i<=n;++i) root[i]=++num;
	for(int i=1;i<=m;++i){
		int x,y,z;
		read(x),read(y),read(z);
		X[i]=x,Y[i]=y,Z[i]=z;
		val[i]=Z[i];
	}

	sort(val+1,val+m+1);
	cnt=unique(val+1,val+m+1)-val-1;
	for(int i=1;i<=m;++i){
		int x=X[i],y=Y[i];
		int z=lower_bound(val+1,val+cnt+1,Z[i])-val;
		int p=lca(x,y);
		insert(root[x],1,cnt,z,1);
		insert(root[y],1,cnt,z,1);
		insert(root[p],1,cnt,z,-1);
		if(f[p][0]) insert(root[f[p][0]],1,cnt,z,-1);
	}

	dfs(1);
	for(int i=1;i<=n;++i)
		printf("%d\n",val[ans[i]]);
	return 0;
}