Codeforces 600E Lomsat gelral(dsu on tree)

  dsu on tree板子题。这个trick保证均摊O(nlogn)的复杂度,要求资瓷O(1)将一个元素插入集合,清空集合时每个元素O(1)删除。(当然log的话就变成log^2了)

  具体的,每次先遍历轻儿子的子树,暴力求得所需信息,每遍历完一棵轻子树都将其信息清空。然后遍历重子树,暴力求得所需信息,保留信息,再重新遍历轻子树将信息合并,最后加上根本身得到原子树的信息。

  复杂度证明考虑每个点的信息被统计的次数,显然这只与其到根的路径上轻边条数有关,于是复杂度O(nlogn)。

#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;
#define ll long long
#define N 100010
char getc(){char c=getchar();while ((c<'A'||c>'Z')&&(c<'a'||c>'z')&&(c<''||c>'')) c=getchar();return c;}
int gcd(int n,int m){return m==?n:gcd(m,n%m);}
int read()
{
int x=,f=;char c=getchar();
while (c<''||c>'') {if (c=='-') f=-;c=getchar();}
while (c>=''&&c<='') x=(x<<)+(x<<)+(c^),c=getchar();
return x*f;
}
int n,a[N],p[N],fa[N],size[N],son[N],cnt[N],mx,t;
ll ans[N],cur;
struct data{int to,nxt;
}edge[N<<];
void addedge(int x,int y){t++;edge[t].to=y,edge[t].nxt=p[x],p[x]=t;}
void make(int k)
{
size[k]=;
for (int i=p[k];i;i=edge[i].nxt)
if (edge[i].to!=fa[k])
{
fa[edge[i].to]=k;
make(edge[i].to);
size[k]+=size[edge[i].to];
if (size[edge[i].to]>size[son[k]]) son[k]=edge[i].to;
}
}
void update(int x,int op)
{
cnt[x]+=op;
if (op==)
{
if (cnt[x]>mx) mx=cnt[x],cur=;
if (cnt[x]>=mx) cur+=x;
}
else mx=cur=;
}
void add(int k,int op)
{
update(a[k],op);
for (int i=p[k];i;i=edge[i].nxt)
if (edge[i].to!=fa[k]) add(edge[i].to,op);
}
void dfs(int k)
{
for (int i=p[k];i;i=edge[i].nxt)
if (edge[i].to!=fa[k]&&edge[i].to!=son[k]) dfs(edge[i].to),add(edge[i].to,-);
if (son[k]) dfs(son[k]);
for (int i=p[k];i;i=edge[i].nxt)
if (edge[i].to!=fa[k]&&edge[i].to!=son[k]) add(edge[i].to,);
update(a[k],);ans[k]=cur;
}
int main()
{
#ifndef ONLINE_JUDGE
freopen("600E.in","r",stdin);
freopen("600E.out","w",stdout);
const char LL[]="%I64d\n";
#else
const char LL[]="%lld\n";
#endif
n=read();
for (int i=;i<=n;i++) a[i]=read();
for (int i=;i<n;i++)
{
int x=read(),y=read();
addedge(x,y),addedge(y,x);
}
make();
dfs();
for (int i=;i<=n;i++) printf("%I64d ",ans[i]);
return ;
}
上一篇:Codeforces 600E - Lomsat gelral(树上启发式合并)


下一篇:CF 600E. Lomsat gelral(dsu on tree)