CF600E Lomsat Gelral

2018-10-08 09:15:19


题意:给一棵带点权树,求每个点的子树中的众数之和


对每个点维护一棵权值线段树, $dfs$ 过程中合并子树信息就好了orz

#include<cstdio>
#include<cstring>
#include<cctype>
#include<algorithm>
#define ls t[now].l
#define rs t[now].r
#define reg register
using namespace std;
typedef long long ll;
const int N=1e5+5;
struct node
{
    int to,nxt;
}edge[N<<1];
struct Tree
{
    int l,r; ll ans,sum;
}t[N*50];
int n,c[N],num,head[N],rt[N],cnt;
ll ans[N];
inline int read()
{
    int x=0,w=1;
    char c=getchar();
    while (!isdigit(c)&&c!='-') c=getchar();
    if (c=='-') c=getchar(),w=-1;
    while (isdigit(c))
    {
        x=(x<<1)+(x<<3)+c-'0';
        c=getchar();
    }
    return x*w;
}
inline void add_edge(int from,int to)
{
    edge[++num]=(node){to,head[from]};
    head[from]=num;
}
inline void pushup(int now)
{
    if (t[ls].sum>t[rs].sum) t[now].sum=t[ls].sum,t[now].ans=t[ls].ans;
    else if (t[ls].sum<t[rs].sum) t[now].sum=t[rs].sum,t[now].ans=t[rs].ans;
    else t[now].sum=t[ls].sum,t[now].ans=t[ls].ans+t[rs].ans;
}
void insert(int &now,int l,int r,int x,int c)
{
    if (!now) now=++cnt;
    if (l==r) {t[now].ans=l; t[now].sum+=c; return;}
    int mid=(l+r)>>1;
    if (x<=mid) insert(ls,l,mid,x,c);
    else insert(rs,mid+1,r,x,c);
    pushup(now);
}
int merge(int a,int b,int l,int r)
{
    if (!a) return b; if (!b) return a;
    if (l==r) {t[a].sum+=t[b].sum; t[a].ans=l; return a;}
    int mid=(l+r)>>1;
    t[a].l=merge(t[a].l,t[b].l,l,mid);
    t[a].r=merge(t[a].r,t[b].r,mid+1,r);
    pushup(a); return a;
}
void dfs(int k,int fa)
{
    for (reg int i=head[k];i;i=edge[i].nxt)
    {
        int v=edge[i].to;
        if (v==fa) continue;
        dfs(v,k); rt[k]=merge(rt[k],rt[v],1,N-5);
    }
    insert(rt[k],1,N-5,c[k],1);
    ans[k]=t[rt[k]].ans;
}
int main()
{
    n=read(); cnt=n;
    for (reg int i=1;i<=n;i++) c[i]=read(),rt[i]=i;
    for (reg int i=1;i<n;i++)
    {
        int x=read(),y=read();
        add_edge(x,y); add_edge(y,x);
    }
    dfs(1,0);
    for (reg int i=1;i<=n;i++) printf("%lld ",ans[i]);
    return 0;
}