记录编号	561106	评测结果	AAAAAAAAAA
题目名称	像化哲敬一样	最终得分	100
用户昵称	瑆の時間~無盡輪迴·林蔭	是否通过	通过
代码语言	C++	运行时间	9.682 s
提交时间	2021-06-20 18:48:06	内存使用	402.76 MiB

    #include<iostream>
    #include<cstdio>
    #include<vector>
    using namespace std;
    int val[20000001],ls[20000001],rs[20000001],dep[100001];
    int fa[100001][26];
    int Max[20000001];
    int rt[20000001];
    int ans[100001];
    int xi[500001],yi[500001],zi[500001];
    int n,m,a1,a2,a3,tot,R;
    vector<int> b[100001];
    void BZ()
    {
    	for(int i=1;i<=25;i++)
    	{
    		for(int j=1;j<=n;j++)
    		{
    			fa[j][i]=fa[fa[j][i-1]][i-1];
    		}
    	}
    }
    void DFS(int x,int f)
    {
    	dep[x]=dep[f]+1;
    	fa[x][0]=f;
    	for(int i=0;i<b[x].size();i++)
    	{
    		int to=b[x][i];
    		if(to==f)
    			continue;
    		DFS(to,x);
    	}
    }
    void pushup(int x)
    {
    	if(val[ls[x]]>=val[rs[x]])
    	{
    		val[x]=val[ls[x]];
    		Max[x]=Max[ls[x]];
    	}
    	else
    	{
    		val[x]=val[rs[x]];
    		Max[x]=Max[rs[x]];
    	}
    	if(val[x]==0)
    	{
    		Max[x]=0;
    	}
    }
    int Merge(int l,int r,int u,int v)
    {
    	if(!u||!v)
    	{
    		return u+v;
    	}
    	if(l==r)
    	{
    		val[u]+=val[v];
    		Max[u]=l;
    		return u;
    	}
    	int mid=(l+r)>>1;
    	ls[u]=Merge(l,mid,ls[u],ls[v]);
    	rs[u]=Merge(mid+1,r,rs[u],rs[v]);
    	pushup(u);
    	return u;
    }
    void ADD(int &x,int l,int r,int p,int v)
    {
    	if(!x)
    	{
    		x=++tot;
    	}
    	if(l==r)
    	{
    		val[x]+=v;
    		Max[x]=l;
    		return;
    	}
    	int mid=(l+r)>>1;
    	if(p<=mid)
    		ADD(ls[x],l,mid,p,v);
    	else
    		ADD(rs[x],mid+1,r,p,v);
    	pushup(x);
    }
    int LCA(int x,int y)
    {
    	if(dep[x]<dep[y])
    		swap(x,y);
    	for(int i=25;i>=0;i--)
    	{
    		if(dep[fa[x][i]]>=dep[y])
    			x=fa[x][i];
    	}
    	if(x==y)
    	{
    		return x;
    	}
    	for(int i=25;i>=0;i--)
    	{
    		if(fa[x][i]!=fa[y][i])
    		{
    			x=fa[x][i];
    			y=fa[y][i];
    		}
    	}
    	return fa[x][0];
    }
    void Work(int x,int f)
    {
    	for(int i=0;i<b[x].size();i++)
    	{
    		int to=b[x][i];
    		if(to==f)
    			continue;
    		Work(to,x);
    		rt[x]=Merge(1,R,rt[x],rt[to]);
    	}
    	ans[x]=Max[rt[x]];
    }
    int main()
    {
    	freopen("ASVIGIL.in","r",stdin);
    	freopen("ASVIGIL.out","w",stdout);
    	scanf("%d%d",&n,&m);
    	for(int i=1;i<n;i++)
    	{
    		scanf("%d%d",&a1,&a2);
    		b[a1].push_back(a2);
    		b[a2].push_back(a1);
    	}
    	DFS(1,0);
    	BZ();
    	for(int i=1;i<=m;i++)
    	{
    		scanf("%d%d%d",&xi[i],&yi[i],&zi[i]);
    		R=max(R,zi[i]);
    	}
    	for(int i=1;i<=m;i++)
    	{
    		a1=xi[i];
    		a2=yi[i];
    		a3=zi[i];
    		int L=LCA(a1,a2);
    		ADD(rt[a1],1,R,a3,1);
    		ADD(rt[a2],1,R,a3,1);
    		ADD(rt[L],1,R,a3,-1);
    		if(fa[L][0])
    		{
    			ADD(rt[fa[L][0]],1,R,a3,-1);
    		}
    	}
    	Work(1,0);
    	for(int i=1;i<=n;i++)
    	{
    		printf("%d ",ans[i]);
    	}
    	return 0;
    }