洛咕 P4556 [Vani有约会]雨天的尾巴

终于把考试题清完了。。。又复活了。。。

树上差分，合并用线段树合并，但是空间会炸。

某大佬：lca和fa[lca]减得时候一定已经存在这个节点了，所以放进vector里，合并完之后减掉就好了。。。

玄学优化就过了。。

// luogu-judger-enable-o2
#include<bits/stdc++.h>
#define il inline
#define vd void
#define N 100000
typedef long long ll;
il int gi(){
    int x=0,f=1;
    char ch=getchar();
    while(!isdigit(ch)){
        if(ch=='-')f=-1;
        ch=getchar();
    }
    while(isdigit(ch))x=x*10+ch-'0',ch=getchar();
    return x*f;
}
int fir[100010],dis[200010],nxt[200010],id,siz[100010],son[100010],fa[100010],top[100010],dep[100010];
il vd link(int a,int b){nxt[++id]=fir[a],fir[a]=id,dis[id]=b;}
typedef struct node* point;
struct node{
    int mx,qwq;
    point ls,rs;
    node(){mx=0,qwq=0,ls=NULL,rs=NULL;}
};
il vd dfs(int x){
    siz[x]=1;
    for(int i=fir[x];i;i=nxt[i]){
        if(fa[x]==dis[i])continue;
        dep[dis[i]]=dep[x]+1;fa[dis[i]]=x;
        dfs(dis[i]);siz[x]+=siz[dis[i]];
        if(siz[dis[i]]>siz[son[x]])son[x]=dis[i];
    }
}
il vd dfs2(int x,int tp){
    top[x]=tp;
    if(son[x])dfs2(son[x],tp);
    for(int i=fir[x];i;i=nxt[i])if(dis[i]!=fa[x]&&dis[i]!=son[x])dfs2(dis[i],dis[i]);
}
il int lca(int a,int b){
    while(top[a]^top[b])
        if(dep[top[a]]>dep[top[b]])a=fa[top[a]];
        else b=fa[top[b]];
    return dep[a]<dep[b]?a:b;
}
#define mid ((l+r)>>1)
il vd upd(const point&x){
    if(x->ls==NULL)x->mx=x->rs->mx,x->qwq=x->rs->qwq;
    else if(x->rs==NULL)x->mx=x->ls->mx,x->qwq=x->ls->qwq;
    else if(x->ls->mx>=x->rs->mx)x->mx=x->ls->mx,x->qwq=x->ls->qwq;
    else x->mx=x->rs->mx,x->qwq=x->rs->qwq;
}
il vd update(point&x,int l,int r,const int&p,const int&s){
    if(x==NULL)x=new node;
    if(l==r){x->mx+=s,x->qwq=l;return;}
    if(p<=mid)update(x->ls,l,mid,p,s);
    else update(x->rs,mid+1,r,p,s);
    upd(x);
}
point rt[100010];
int ans[100010];
il vd merge(point&x,point y,int l=1,int r=N){
    if(x==NULL){x=y;return;}
    else if(y==NULL)return;
    if(x->ls==NULL&&x->rs==NULL){x->mx+=y->mx;return;}
    merge(x->ls,y->ls,l,mid),merge(x->rs,y->rs,mid+1,r);
    upd(x);
}
std::vector<int>S[100010];
il vd Merge(int x){
    for(int i=fir[x];i;i=nxt[i]){
        if(fa[x]==dis[i])continue;
        Merge(dis[i]);
        merge(rt[x],rt[dis[i]]);
    }
    for(int i=0;i<S[x].size();++i)update(rt[x],1,N,S[x][i],-1);
    if(rt[x]!=NULL&&rt[x]->mx)ans[x]=rt[x]->qwq;
}
int main(){
#ifndef ONLINE_JUDGE
    freopen("4556.in","r",stdin);
    freopen("4556.out","w",stdout);
#endif
    int n=gi(),m=gi(),u,v,w,l;
    for(int i=1;i<n;++i)u=gi(),v=gi(),link(u,v),link(v,u);
    dfs(1);dfs2(1,1);
    while(m--){
        u=gi(),v=gi(),w=gi();l=lca(u,v);
        update(rt[u],1,N,w,1);update(rt[v],1,N,w,1);
        S[l].push_back(w);
        S[fa[l]].push_back(w);
    }
    Merge(1);
    for(int i=1;i<=n;++i)printf("%d
",ans[i]);
    return 0;
}