萌新T了qwq
查看原帖
萌新T了qwq
455558
Imiya楼主2022/4/21 20:21
#include<iostream>
using namespace std;
const int N=100100,Log=30;
inline int read(){
    int r=0,i=getchar();
    while(i<'0'||i>'9')i=getchar();
    while(i>='0'&&i<='9')r=(r<<1)+(r<<3)+(i^48),i=getchar();
    return r;
}
int nex[N<<1],to[N<<1],head[N],fa[N][Log],dep[N],son[N],bro[N];
inline void new_edge(int id,int u,int v){
    to[id]=v;
    nex[id]=head[u];
    head[u]=id;
}
inline void new_rel(int u,int v){
    bro[v]=son[u];
    son[u]=v;
    fa[v][0]=u;
}
int n,m;
void prepare(int nd,int d){
    dep[nd]=d;
    for(int i=head[nd];i;i=nex[i]){
        if(dep[to[i]])continue;
        new_rel(nd,to[i]);
        for(int j=1;j<Log;j++)fa[to[i]][j]=fa[fa[to[i]][j-1]][j-1];
        prepare(to[i],d+1);
    }
}
inline int get_lca(int u,int v){
    if(dep[u]<dep[v])swap(u,v);
    int dif=dep[u]-dep[v];
    for(int i=0;dif;dif>>=1,i++)if(dif&1)u=fa[u][i];
    if(u==v)return u;
    for(int i=Log-1;i>=0;i--)if(fa[u][i]!=fa[v][i])u=fa[u][i],v=fa[v][i];
    return fa[u][0];
}
int L[N*Log],R[N*Log],ls[N*Log],rs[N*Log],maxv[N*Log],maxi[N*Log],top[N],cnt;
inline int New(int l,int r,int c1,int c2,int v,int id){
    L[++cnt]=l,R[cnt]=r,ls[cnt]=c1,rs[cnt]=c2,maxv[cnt]=v,maxi[cnt]=id;
    return cnt;
}
inline int new_tree(){return New(1,N-1,0,0,0,0);}
inline void push_up(int nd){
    if(!maxv[ls[nd]]&&!maxv[rs[nd]])maxi[nd]=0;
    else if(maxv[ls[nd]]>=maxv[rs[nd]])maxv[nd]=maxv[ls[nd]],maxi[nd]=maxi[ls[nd]];
    else maxv[nd]=maxv[rs[nd]],maxi[nd]=maxi[rs[nd]];
}
void add(int nd,int pos,int k){
    if(L[nd]==R[nd]){
        maxi[nd]=pos;
        maxv[nd]+=k;
        return;
    }
    int mid=(L[nd]+R[nd])>>1;
    if(pos<=mid){
        if(!ls[nd])ls[nd]=New(L[nd],mid,0,0,0,0);
        add(ls[nd],pos,k);
    }
    else{
        if(!rs[nd])rs[nd]=New(mid+1,R[nd],0,0,0,0);
        add(rs[nd],pos,k);
    }
    push_up(nd);
}
int merge(int u,int v){
    if(!u)return v;
    if(!v)return u;
    if(L[u]==R[u]){
        maxv[u]+=maxv[v];
        return u;
    }
    ls[u]=merge(ls[u],ls[v]);
    rs[u]=merge(rs[u],rs[v]);
    push_up(u);
    return u;
}
void init(){
    cin>>n>>m;
    for(int i=1;i<n;i++){
        int u=read(),v=read();
        new_edge(i<<1,u,v);
        new_edge(i<<1|1,v,u);
    }
    prepare(1,1);
    for(int i=1;i<=n;i++)top[i]=new_tree();
    for(int i=1;i<=m;i++){
        int x=read(),y=read(),z=read();
        int lca=get_lca(x,y);
//        cout<<x<<' '<<y<<' '<<lca<<endl;
        add(top[x],z,1);
        add(top[y],z,1);
        add(top[lca],z,-1);
        if(fa[lca][0])add(top[fa[lca][0]],z,-1);
    }
}
int ans[N];
void get_sum(int nd){
    for(int i=son[nd];i;i=bro[i]){
        get_sum(top[i]);
        merge(top[nd],top[i]);
    }
    ans[nd]=maxi[top[nd]];
}
int main(){
    // freopen("read.in","r",stdin);
    init();
    get_sum(1);
    for(int i=1;i<=n;i++)printf("%d\n",ans[i]);
//    for(int i=1;i<=n;i++)printf("%d ",fa[i][0]);
    return 0;
}
2022/4/21 20:21
加载中...