线段树合并

考虑对每个节点开权值线段树，所有操作结束后在每个节点上查询数量最多的粮食编号。由于 $n,m$ 同阶，时空复杂度同为 $O(n^2 \log n)$，无法接受。

差分树链加操作，在 $x_i,y_i$ 处令权值线段树 $z_i$ 增加 $1$，在 $\operatorname{lca}(x_i,y_i)$ 和这个节点的父亲处令权值线段树 $z_i$ 减去 $1$，对所有权值线段树的添加、删除次数降低到 $O(n)$ 等级。

在节点 $i$ 继承其所有儿子节点的线段树信息后完成对位置 $i$ 的所有修改操作即可获得所有操作结束后节点 $i$ 的权值线段树信息，使用线段树合并维护。

struct Segment{int w,x,ls,rs;}s[100'005*20];//w:最大权值 x:最大权值来源
void pushup(int u){
    s[u].w=max(s[s[u].ls].w,s[s[u].rs].w);
    if(s[u].w==s[s[u].ls].w) s[u].x=s[s[u].ls].x;
    else s[u].x=s[s[u].rs].x;
}
int merge(int ul,int ur,int l,int r){
    if(ul==0||ur==0) return ul+ur;
    if(l==r) return s[ul].w+=s[ur].w,ul;
    int mid=(l+r)>>1;
    s[ul].ls=merge(s[ul].ls,s[ur].ls,l,mid);
    s[ul].rs=merge(s[ul].rs,s[ur].rs,mid+1,r);
    pushup(ul);
    return ul;
}

总体时间复杂度 $O(n \log n)$，空间复杂度 $O(n \log n)$。

#include<bits/stdc++.h>
using namespace std;
constexpr int lim=100'000;
struct Segment{int w,x,ls,rs;}s[100'005*20];
vector<int> v[100'005],add[100'005],del[100'005];
int n,m,seg,d[100'005],ro[100'005],ans[100'005],f[20][100'005];
void dfs(int x,int las){
    d[x]=d[las]+1,f[0][x]=las;
    for(int i:v[x]) if(i!=las) dfs(i,x);
}
int lca(int x,int y){
    if(d[x]<d[y]) swap(x,y);
    for(int i=__lg(d[x]);~i;i--) if(d[f[i][x]]>=d[y]) x=f[i][x];
    if(x==y) return x;
    for(int i=__lg(d[x]);~i;i--) if(f[i][x]!=f[i][y]) x=f[i][x],y=f[i][y];
    return f[0][x];
}
void pushup(int u){
    s[u].w=max(s[s[u].ls].w,s[s[u].rs].w);
    if(s[u].w==s[s[u].ls].w) s[u].x=s[s[u].ls].x;
    else s[u].x=s[s[u].rs].x;
}
void update(int &u,int l,int r,int p,int k){
    if(u==0) u=++seg;
    if(l==r) return s[u].w+=k,s[u].x=l,void();
    int mid=(l+r)>>1;
    if(p<=mid) update(s[u].ls,l,mid,p,k);
    else update(s[u].rs,mid+1,r,p,k);
    pushup(u);
}
int merge(int ul,int ur,int l,int r){
    if(ul==0||ur==0) return ul+ur;
    if(l==r) return s[ul].w+=s[ur].w,ul;
    int mid=(l+r)>>1;
    s[ul].ls=merge(s[ul].ls,s[ur].ls,l,mid);
    s[ul].rs=merge(s[ul].rs,s[ur].rs,mid+1,r);
    pushup(ul);
    return ul;
}
void segsort(int x,int las){
    for(int i:v[x]) if(i!=las) segsort(i,x),ro[x]=merge(ro[x],ro[i],1,lim);
    for(int i:add[x]) update(ro[x],1,lim,i,1);
    for(int i:del[x]) update(ro[x],1,lim,i,-1);
    ans[x]=s[ro[x]].w ? s[ro[x]].x:0;
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin>>n>>m;
    for(int i=1;i<=n-1;i++){
        static int x,y;
        cin>>x>>y;
        v[x].push_back(y);
        v[y].push_back(x);
    }
    dfs(1,0);
    for(int i=1;(1<<i)<=n;i++)
        for(int j=1;j<=n;j++) f[i][j]=f[i-1][f[i-1][j]];
    for(int i=1;i<=m;i++){
        static int x,y,k,poi;
        cin>>x>>y>>k,poi=lca(x,y);
        add[x].push_back(k);
        add[y].push_back(k);
        del[poi].push_back(k);
        del[f[0][poi]].push_back(k);
    }
    segsort(1,0);
    for(int i=1;i<=n;i++) cout<<ans[i]<<'\n';
    return 0;
}