题目描述

深绘里一直很讨厌雨天。

灼热的天气穿透了前半个夏天，后来一场大雨和随之而来的洪水，浇灭了一切。

虽然深绘里家乡的小村落对洪水有着顽固的抵抗力，但也倒了几座老房子，几棵老树被连根拔起，以及田地里的粮食被弄得一片狼藉。

无奈的深绘里和村民们只好等待救济粮来维生。

不过救济粮的发放方式很特别。

有 n 个点，形成一个树状结构。

有 m 次发放操作，每次选择两个点 x,y，对 x 到 y 的路径上（包括 x,y）的每个点发放一袋 z 类型的物品。

求完成所有发放操作后，每个点存放最多的是哪种类型的物品。

样例

输入
5 3
1 2
3 1
3 4
5 3
2 3 3
1 5 2
3 3 3

输出
2
3
3
0
2

算法1

(线段树合并) $O(n^2)$

树上差分思想，每个点开一个权值线段树，修改等于在链两端下标z处+1，在LCA和LCA的父亲处−1，然后自底向上合并。LCA可以直接Tarjan求。

然而要算算空间。动态开点总数n log n（认为n,m,n,m,值域同阶），每个点维护左右儿子和区间max，int占4字节，总共快80MB了，再加上邻接表，栈空间什么乱七八糟的，虽说应该勉强不会炸，但也够卡了。

有一个小优化：我们在LCA和LCA父亲处做减法的时候，对应下标的节点肯定已经存在了。所以做减法的部分直接用vector（手写链表）存下需要−1−1的下标即可。线段树部分的空间马上少了一半，一点也不卡了。

代码短（1.8k），常数有点大，比树剖慢，跟线段树合并的空间复杂度大于树剖不无关系。

C++ 代码

#include<bits/stdc++.h>
#define LL long long
#define RG register
#define R RG int
#define G if(++ip==ie)fread(ip=buf,1,SZ,stdin)
#define Pushup mx[x]=max(mx[lc[x]],mx[rc[x]])
using namespace std;
const int SZ=1<<19,N=1e5+1,M=6e5+9,L=3.5e6;
char buf[SZ],*ie=buf+SZ,*ip=ie-1;
int p=1,ehe[N],qhe[N],dhe[N],ne[M],to[M],id[M];bool fl[M];//注意这里的三个表头
int q,rt[N],lc[L],rc[L],mx[L];
int tmp,updv=1,f[N],fa[N],ans[N];
inline int in(){
    G;while(*ip<'-')G;
    R x=*ip&15;G;
    while(*ip>'-'){x*=10;x+=*ip&15;G;}
    return x;
}
inline int gf(R x){//并查集
    return x==f[x]?x:f[x]=gf(f[x]);
}
inline int qry(R x){//找出最大值下标
    R l=0,r=N,m;
    while(l<r){
        m=(l+r)>>1;
        if(mx[lc[x]]>=mx[rc[x]])r=m,x=lc[x];
        else l=m+1,x=rc[x];
    }
    return l;
}
void upd(R&x,R l,R r){//单点更新
    if(!x)x=++q;
    if(l==r){mx[x]+=updv;return;}
    R m=(l+r)>>1;
    tmp<=m?upd(lc[x],l,m):upd(rc[x],m+1,r);
    Pushup;
}
void mer(R x,R y,R l,R r){//线段树合并
    if(l==r){mx[x]+=mx[y];return;}
    R m=(l+r)>>1;
    if(lc[x]&&lc[y])mer(lc[x],lc[y],l,m);
    else lc[x]+=lc[y];
    if(rc[x]&&rc[y])mer(rc[x],rc[y],m+1,r);
    else rc[x]+=rc[y];
    Pushup;
}
void dfs(R x){//一遍dfs一气呵成
    for(R i=ehe[x];i;i=ne[i])
        if(to[i]!=fa[x]){
            fa[to[i]]=x;dfs(to[i]);
            mer(rt[x],rt[to[i]],1,N);
        }
    for(R i=qhe[x];i;i=ne[i])//Tarjan-LCA
        if(fl[i>>1]){//减法直接链表存下标
            ne[++p]=dhe[tmp=gf(to[i])];id[dhe[tmp]=p]=id[i];
            ne[++p]=dhe[tmp=fa[tmp]]  ;id[dhe[tmp]=p]=id[i];
        }
        else fl[i>>1]=1;
    for(R i=dhe[x];i;i=ne[i])//减法开始
        tmp=id[i],upd(rt[x],0,N);
    ans[x]=qry(rt[x]);f[x]=fa[x];
}
int main(){
    R n=in(),m=in(),i,x,y;
    for(i=1;i<n;++i){
        x=in();y=in();
        ne[++p]=ehe[x];to[ehe[x]=p]=y;
        ne[++p]=ehe[y];to[ehe[y]=p]=x;
    }
    for(i=1;i<=n;++i)
        f[i]=i,rt[i]=++q;//蒟蒻的这种merge写法需要根节点非空
    for(i=1;i<=m;++i){
        x=in();y=in();tmp=in();
        upd(rt[x],0,N);upd(rt[y],0,N);
        ne[++p]=qhe[x];to[qhe[x]=p]=y;id[p]=tmp;
        ne[++p]=qhe[y];to[qhe[y]=p]=x;id[p]=tmp;
    }
    updv=-1;dfs(1);
    for(i=1;i<=n;++i)printf("%d\n",ans[i]);
    return 0;
}