不知道为什么 RE 了,并且在本地和洛谷 IDE 都可以正常运行
#include <iostream>
#include <cstdio>
#include <vector>
#define N 100011
#define ls tr[k].l
#define rs tr[k].r
using namespace std;
struct Node
{
int l;
int r;
int sum; //数量
int ans; //颜色
}tr[N<<5];
int rt[N<<5],dep[N],ans_sum[N],fa[N][22],cnt;
vector<int>T[N];
void push_up(int k)
{
if(tr[ls].sum>tr[rs].sum)
{
tr[k].sum=tr[ls].sum;
tr[k].ans=tr[ls].ans;
}
if(tr[rs].sum>tr[ls].sum)
{
tr[k].sum=tr[rs].sum;
tr[k].ans=tr[rs].ans;
}
if(tr[ls].sum==tr[rs].sum)
{
tr[k].sum=tr[ls].sum;
tr[k].ans=min(tr[ls].ans,tr[rs].ans);
}
}
int update(int &now,int l,int r,int pos,int v)
{
if(!now) now=++cnt;
if(l==r)
{
tr[now].sum+=v;
tr[now].ans=l;
return 0;
}
int mid=(l+r)>>1;
if(pos<=mid) update(tr[now].l,l,mid,pos,v);
else update(tr[now].r,mid+1,r,pos,v);
push_up(now);
}
int merge(int a,int b,int l,int r)
{
if(!a) return b;
if(!b) return a;
if(l==r)
{
tr[a].sum+=tr[b].sum;
tr[a].ans=l;
return a;
}
int mid=(l+r)>>1;
tr[a].l=merge(tr[a].l,tr[b].l,l,mid);
tr[a].r=merge(tr[a].r,tr[b].r,mid+1,r);
push_up(a);
return a;
}
void dfs(int u,int f)
{
dep[u]=dep[f]+1;
fa[u][0]=f;
for(int i=1;(1<<i)<=dep[u];++i) fa[u][i]=fa[fa[u][i-1]][i-1];
for(int i=0;i<T[u].size();++i)
{
int v=T[u][i];
if(v==f) continue;
dfs(v,u);
}
}
int LCA(int x,int y)
{
if(dep[x]<dep[y]) swap(x,y);
for(int i=21;i>=0;--i)
if(dep[fa[x][i]]>=dep[y])
x=fa[x][i];
if(x==y) return x;
for(int i=21;i>=0;--i)
if(fa[x][i]!=fa[y][i])
{
x=fa[x][i];
y=fa[y][i];
}
return fa[x][0];
}
void get_ans(int u,int f)
{
for(int i=0;i<T[u].size();++i)
{
int v=T[u][i];
if(v==f) continue;
get_ans(v,u);
merge(rt[u],rt[v],1,N);
}
ans_sum[u]=tr[rt[u]].ans;
}
int main()
{
// freopen(".in","r",stdin);
// freopen(".out","w",stdout);
int n,m;
scanf("%d %d",&n,&m);
for(int i=1;i<=n;++i) rt[i]=i,++cnt;
for(int i=1;i<n;++i)
{
int x,y;
scanf("%d %d",&x,&y);
T[x].push_back(y);
T[y].push_back(x);
}
dfs(1,0);
for(int i=1;i<=m;++i)
{
int x,y,z;
scanf("%d %d %d",&x,&y,&z);
int A=LCA(x,y);
update(rt[x],1,N,z,1);
update(rt[y],1,N,z,1);
update(rt[A],1,N,z,-1);
update(rt[fa[A][0]],1,N,z,-1);
}
get_ans(1,0);
for(int i=1;i<=n;++i) printf("%d\n",ans_sum[i]);
return 0;
}