CF600E Lomsat Gelral

题意：给一棵带点权树，求每个点的子树中的众数之和 ------------ 对每个点维护一棵权值线段树，$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; } ```