【CF600E】Lomsat gelral(dsu on tree)
题面
洛谷
CF题面自己去找找吧。
题解
\(dsu\ on\ tree\)板子题
其实就是做子树询问的一个较快的方法。
对于子树的询问,我们不难想到子树就是\(dfs\)序上的连续一段,
可以把树转化成序列再用莫队来解。
其实可以对树进行树链剖分,然后暴力+优化来解
具体的做法就是:
递归处理轻儿子,计算轻儿子答案,
然后消去轻儿子对于答案的影响。
然后递归处理重儿子,不消去影响,最后加入所有轻儿子贡献,计算答案。
复杂度?
每个点会被消去影响的时候,一定是某个父亲是轻儿子
而树链剖分保证了这个次数是\(log\)次
所以复杂度是\(O(nlogn)\)优于莫队的\(O(n\sqrt n)\)
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<set>
#include<map>
#include<vector>
#include<queue>
using namespace std;
#define ll long long
#define RG register
#define MAX 111111
inline int read()
{
RG int x=0,t=1;RG char ch=getchar();
while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();
if(ch=='-')t=-1,ch=getchar();
while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar();
return x*t;
}
struct Line{int v,next;}e[MAX<<1];
int h[MAX],cnt=1;
inline void Add(int u,int v){e[cnt]=(Line){v,h[u]};h[u]=cnt++;}
int size[MAX],hson[MAX],dep[MAX],fa[MAX];
ll ans[MAX],sum[MAX];
int num[MAX],top,c[MAX],n;
bool vis[MAX];
void dfs1(int u,int ff)
{
fa[u]=ff;dep[u]=dep[ff]+1;size[u]=1;
for(int i=h[u];i;i=e[i].next)
{
int v=e[i].v;if(v==ff)continue;
dfs1(v,u);size[u]+=size[v];
if(size[v]>size[hson[u]])hson[u]=v;
}
}
void update(int u,int ff,int opt)
{
sum[num[c[u]]]-=c[u];
num[c[u]]+=opt;
sum[num[c[u]]]+=c[u];
if(sum[top+1])++top;
if(!sum[top])--top;
for(int i=h[u];i;i=e[i].next)
if(e[i].v!=ff&&!vis[e[i].v])update(e[i].v,u,opt);
}
void dfs(int u,int ff,int hs)
{
for(int i=h[u];i;i=e[i].next)
if(e[i].v!=ff&&e[i].v!=hson[u])dfs(e[i].v,u,0);
if(hson[u])dfs(hson[u],u,1),vis[hson[u]]=true;
update(u,ff,1);vis[hson[u]]=0;
ans[u]=sum[top];
if(!hs)update(u,ff,-1);
}
int main()
{
n=read();
for(int i=1;i<=n;++i)c[i]=read();
for(int i=1;i<n;++i)
{
int u=read(),v=read();
Add(u,v);Add(v,u);
}
dfs1(1,0);dfs(1,0,1);
for(int i=1;i<=n;++i)printf("%I64d ",ans[i]);puts("");
return 0;
}