关于dsu on tree过本题

//dsu on tree 做法
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<vector>
#include<cmath>
#include<map>
#include<bitset>
using namespace std;
typedef long long ll;
int n,m;
int dep[100010],top[100010],fa[100010],son[100010],sz[100010];
int tot=0,head[100010];
vector<int> vec[100010];
int ans[100010];
struct EDGE
{
    int nxt,to;
}edge[200010];
void add(int u,int v)
{
    edge[++tot].nxt=head[u];
    edge[tot].to=v;
    head[u]=tot;
}
void dfs1(int x,int f)
{
    sz[x]=1;
    fa[x]=f;
    dep[x]=dep[f]+1;
    for(int i=head[x];i;i=edge[i].nxt)
    {
        int y=edge[i].to;
        if(y==f) continue;
        dfs1(y,x);
        sz[x]+=sz[y];
        if(sz[y]>sz[son[x]]) son[x]=y;
    }
}
void dfs2(int x,int t)
{
    top[x]=t;
    if(son[x]) dfs2(son[x],t);
    for(int i=head[x];i;i=edge[i].nxt)
    {
        int y=edge[i].to;
        if(y==fa[x]||y==son[x]) continue;
        dfs2(y,y);
    }
}
int lca(int x,int y)
{
    int fx=top[x],fy=top[y];
    while(fx!=fy)
    {
        if(dep[fx]>dep[fy]) swap(x,y),swap(fx,fy);
        y=fa[fy],fy=top[y];
    }
    if(dep[x]>dep[y]) swap(x,y);
    return x;
}
int l,r,maxn[400010],pnt[400010];
void pushup(int k)
{
    if(maxn[k<<1]>=maxn[k<<1|1])
        maxn[k]=maxn[k<<1],pnt[k]=pnt[k<<1];
    else
        maxn[k]=maxn[k<<1|1],pnt[k]=pnt[k<<1|1];
}
void build(int k,int l,int r)
{
    if(l==r)
    {
        maxn[k]=0,pnt[k]=l;
        return;
    }
    int mid=(l+r)>>1;
    build(k<<1,l,mid);
    build(k<<1|1,mid+1,r);
    pushup(k);
}
void ask_add(int k,int l,int r,int x,int d)
{
    if(l==r)
    {
        maxn[k]+=d;
        return;
    }
    int mid=(l+r)>>1;
    if(x<=mid) ask_add(k<<1,l,mid,x,d);
    else ask_add(k<<1|1,mid+1,r,x,d);
    pushup(k);
}
void seg_clear(int k,int l,int r)
{
    maxn[k]=0,pnt[k]=l;
    if(l==r) return;
    int mid=(l+r)>>1;
    if(maxn[k<<1]) seg_clear(k<<1,l,mid);
    if(maxn[k<<1|1]) seg_clear(k<<1|1,mid+1,r);
}
void get_ans(int x,int s)
{
    for(int i=0,mn=vec[x].size();i<mn;++i)
    {
        int z=vec[x][i];
        if(z>0)
            ask_add(1,l,r,z,1);
        else
            ask_add(1,l,r,-z,-1);
    }
    for(int i=head[x];i;i=edge[i].nxt)
    {
        int y=edge[i].to;
        if(y==fa[x]||y==s) continue;
        get_ans(y,s);
    }
}
void dfs(int x)
{
    for(int i=head[x];i;i=edge[i].nxt)
    {
        int y=edge[i].to;
        if(y==fa[x]||y==son[x]) continue;
        dfs(y);
    }
    if(son[x]) dfs(son[x]);
    get_ans(x,son[x]);
    if(maxn[1]) ans[x]=pnt[1];
    if(x==son[fa[x]]) return;
    seg_clear(1,l,r);
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<n;++i)
    {
        int u,v;scanf("%d%d",&u,&v);
        add(u,v),add(v,u);
    }
    dfs1(1,0),dfs2(1,1);
    l=100000,r=1;
    for(int i=1;i<=m;++i)
    {
        int u,v,z;scanf("%d%d%d",&u,&v,&z);
        vec[u].push_back(z),vec[v].push_back(z);
        int anc=lca(u,v);
        vec[anc].push_back(-z),vec[fa[anc]].push_back(-z);
        r=max(r,z),l=min(l,z);
    }
    build(1,l,r);
    dfs(1);
    for(int i=1;i<=n;++i)
    {
        printf("%d\n",ans[i]);
    }
    return 0;
}