求调题dsu on tree
  • 板块灌水区
  • 楼主hegm
  • 当前回复1
  • 已保存回复1
  • 发布时间2022/9/29 10:36
  • 上次更新2023/10/27 09:34:52
查看原帖
求调题dsu on tree
331947
hegm楼主2022/9/29 10:36
#include<bits/stdc++.h>
#define int long long
#define N 100005
using namespace std;
int read()
{
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
int n,head[N],tot,val[N],cnt,ans[N];
int cal[100005];
struct tree
{
    int from,to,next;
}k[N*2];
struct point
{
    int son,size;
}p[N];
void add(int u,int v)
{
    ++tot;
    k[tot].from=u;
    k[tot].to=v;
    k[tot].next=head[u];
    head[u]=tot;
}
void dfs(int now,int f)
{
    p[now].size=1;
    p[now].son=0;
    for(int i=head[now],to;i;i=k[i].next)
    {
        to=k[i].to;
        if(to==f)continue;
        dfs(to,now);
        p[now].size+=p[to].size;
        if(p[p[now].son].size<p[to].size)p[now].son=to;
    }
}
int dsu(int now,int fa,bool big,bool keep)
{
    if(keep)
    {
        for(int i=head[now],to;i;i=k[i].next)
        {
            to=k[i].to;
            if(to==fa||to==p[i].son)continue;
            dsu(to,now,0,1);
        }
    }
    int tot=0;
    if(p[now].son&&keep)tot+=dsu(p[now].son,now,1,1);
    else if(p[now].son)tot+=dsu(p[now].son,now,1,0);
    for(int i=head[now],to;i;i=k[i].next)
    {
        to=k[i].to;
        if(to==fa||to==p[now].son)continue;
        tot+=dsu(to,now,0,0);
    }
    if(!cal[val[now]])tot++;
    cal[val[now]]++;
    if(keep)ans[now]=tot;
    if(keep&&!big)memset(cal,0,sizeof(cal));
    return tot;
}
signed main()
{
    n=read();
    for(int i=2,u,v;i<=n;i++)
    {
        u=read();v=read();
        add(u,v);
        add(v,u);
    }
    for(int i=1;i<=n;i++)val[i]=read();
    dfs(1,0);
    dsu(1,0,1,1);
    int m=read(),x;
    while(m--)
    {
        x=read();
        cout<<ans[x]<<"\n";
    }
    return 0;
}

疯狂TLE

2022/9/29 10:36
加载中...