线段树合并板子求调!!样例第一行总输出0
查看原帖
线段树合并板子求调!!样例第一行总输出0
581928
jasonliujiahua楼主2023/9/24 12:27
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int maxn=1e5+10,N=100000;
int n,m,cnt,tot,fa[maxn],dep[maxn],sz[maxn],top[maxn],son[maxn];
int rt[maxn<<4],ans[maxn];
struct edge
{
    int u,v,nxt;
}e[maxn<<1];
int head[maxn];
struct node
{
    int ls,rs,sum,num;
}a[maxn<<4];
inline void add(int x,int y)
{
    e[++cnt].u=x;
    e[cnt].v=y;
    e[cnt].nxt=head[x];
    head[x]=cnt;
}
void init()
{
    cin>>n>>m;
    for(int i=1;i<n;i++)
    {
        int x,y;
        cin>>x>>y;
        add(x,y);
        add(y,x);
    }
}
void dfs1(int u,int f)
{
    fa[u]=f,sz[u]=1,dep[u]=dep[f]+1;
    for(int i=head[u];i;i=e[i].nxt)
    {
        int v=e[i].v;
        if(v==f) continue;
        dfs1(v,u);
        sz[u]+=sz[v];
        if(sz[v]>sz[son[u]]) son[u]=v;
    }
}
void dfs2(int u)
{
    if(son[fa[u]]==u) top[u]=top[fa[u]];
    else top[u]=u;
    for(int i=head[u];i;i=e[i].nxt)
    {
        int v=e[i].v;
        if(v==fa[u]) continue;
        dfs2(v);
    }
}
inline int lca(int x,int y)
{
    while(top[x]!=top[y])
    {
        if(dep[top[x]]>dep[top[y]]) x=fa[top[x]];
        else  y=fa[top[y]];
    }
    if(dep[x]<dep[y]) return x;
    return y;
}

inline void pushup(int id)
{
    if(a[a[id].ls].sum>a[a[id].rs].sum)
    {
        a[id].sum=a[a[id].ls].sum;
        a[id].num=a[a[id].ls].num;
    }
    else
    {
        a[id].sum=a[a[id].rs].sum;
        a[id].num=a[a[id].rs].num;
    }
}
inline int modify(int id,int l,int r,int x,int k)
{
    // cout<<id<<" "<<l<<" "<<r<<" "<<x<<" "<<k<<"\n";
    // cout<<"     "<<a[rt[1]].num<<" "<<a[rt[1]].sum<<endl;
    if(!id) id=++tot;
    if(l==r)
    {
        a[id].num=x;
        a[id].sum+=k;
        return id;
    }
    int mid=(l+r)>>1;
    if(x<=mid) a[id].ls=modify(a[id].ls,l,mid,x,k);
    else a[id].rs=modify(a[id].rs,mid+1,r,x,k);
    pushup(id);
    return id;
}
void work()
{
    for(int i=1;i<=m;i++)
    {
        int x,y,z,c;
        cin>>x>>y>>c;
        z=lca(x,y);
        // cout<<x<<" "<<y<<" "<<z<<endl;
        rt[x]=modify(rt[x],1,N,c,1);
        rt[y]=modify(rt[y],1,N,c,1);
        rt[z]=modify(rt[z],1,N,c,-1);
        if(fa[z]) rt[fa[z]]=modify(rt[fa[z]],1,N,c,-1);
    }
}
inline int merge(int id1,int id2,int l,int r)
{
    if(!id1) return id2;
    if(!id2) return id1;
    if(l==r)
    {
        a[id1].sum+=a[id2].sum;
        return id1;
    }
    int mid=(l+r)>>1;
    a[id1].ls=merge(a[id1].ls,a[id2].ls,l,mid);
    a[id1].rs=merge(a[id1].rs,a[id1].rs,mid+1,r);
    pushup(id1);
    return id1;
}
void dfs3(int u)
{
    for(int i=head[u];i;i=e[i].nxt)
    {
        int v=e[i].v;
        if(v==fa[u]) continue;
        dfs3(v);
        rt[u]=merge(rt[u],rt[v],1,N);
    }
    ans[u]=a[rt[u]].num;
    if(!a[rt[u]].sum) ans[u]=0;
}
void output()
{
    for(int i=1;i<=n;i++) cout<<ans[i]<<"\n";
}
void test()
{
    for(int i=1;i<=n;i++)
    {
        printf("rt[%lld]=%lld\n",i,rt[i]);
        printf("sum[%lld]=%lld\n",i,a[rt[i]].sum);
        printf("num[%lld]=%lld\n\n",i,a[rt[i]].num);
    }
}
signed main()
{
    freopen("1.in","r",stdin);
    freopen("1.out","w",stdout);
    init();
    dfs1(1,0);
    dfs2(1);
    work();
    dfs3(1);
    output();
    // test();
    return 0;
}
2023/9/24 12:27
加载中...