BZOJ 3752 世界树

Bertha 。 2022-03-27 07:49 148阅读 0赞

题目链接：http://www.lydsy.com:808/JudgeOnline/problem.php?id=3572

题意：给出一棵树。若干询问。每个询问给出m个点，输出每个点管辖的点的个数。x被y管辖（y在给出的m个点中）是说不存在其他的m个点中的点yy，使得pair<dis(x,yy),yy>   <  pair<dis(x,y),y>。

思路：建立虚树。

const int INF=100000005;
    const int N=333333;
     
    vector<int> gg[N];
    int f[N][20];
    int dep[N];
    int n,m;
     
    int id;
    int dfn[N];
    int size[N];
     
    void DFS(int u,int pre,int d)
    {
        dep[u]=d;
        f[u][0]=pre;
        dfn[u]=++id;
        size[u]=1;
        int i;
        for(i=0;i<SZ(gg[u]);i++)
        {
            int v=gg[u][i];
            if(v!=pre) DFS(v,u,d+1),size[u]+=size[v];
        }
    }
     
     
    int getLca(int u,int v)
    {
        if(dep[u]<dep[v]) swap(u,v);
        int x=dep[u]-dep[v];
        int i;
        for(i=0;i<20;i++) if(x&(1<<i)) u=f[u][i];
        if(u==v) return u;
        for(i=19;i>=0;i--) if(f[u][i]&&f[v][i]&&f[u][i]!=f[v][i])
        {
            u=f[u][i];
            v=f[v][i];
        }
        return f[u][0];
    }
     
    int get(int u,int d)
    {
        int i;
        for(i=19;i>=0;i--) if(dep[f[u][i]]>=d) u=f[u][i];
        return u;
    }
     
     
    pair<int,int> g[N];
    int tot,a[N],b[N];
     
    int ans[N];
     
    int st[N];
     
     
    int cmp(int x,int y)
    {
        return dfn[x]<dfn[y];
    }
     
     
    int fa[N];
     
    void init()
    {
        sort(a+1,a+m+1,cmp);
        int top=0;
        int i;
        for(i=1;i<=m;i++)
        {
            int u=a[i];
            if(!top) fa[st[++top]=u]=0;
            else
            {
                int lca=getLca(st[top],u);
                while(dep[st[top]]>dep[lca])
                {
                    if(dep[st[top-1]]<=dep[lca]) fa[st[top]]=lca;
                    top--;
                }
                if(st[top]!=lca)
                {
                    a[++tot]=lca;
                    g[lca]=MP(INF,0);
                    fa[lca]=st[top];
                    st[++top]=lca;
                }
                fa[u]=lca;
                st[++top]=u;
            }
        }
    }
     
    int dis[N];
    int tmp[N];
     
    void cal()
    {
        sort(a+1,a+tot+1,cmp);
        int i;
        for(i=1;i<=tot;i++)
        {
            int u=a[i];
            tmp[u]=size[u];
            if(i>1) dis[u]=dep[u]-dep[fa[u]];
        }
        for(i=tot;i>1;i--)
        {
            int u=a[i],pre=fa[u];
            g[pre]=min(g[pre],MP(g[u].first+dis[u],g[u].second));
        }
         
        for(i=2;i<=tot;i++)
        {
            int u=a[i],pre=fa[u];
            g[u]=min(g[u],MP(g[pre].first+dis[u],g[pre].second));
        }
     
        for(i=1;i<=tot;i++)
        {
            int u=a[i],pre=fa[u];
            if(i==1) ans[g[u].second]+=n-size[u];
            else
            {
                int x=get(u,dep[pre]+1);
                int sum=size[x]-size[u];
                tmp[pre]-=size[x];
                if(g[pre].second==g[u].second) ans[g[u].second]+=sum;
                else
                {
                    int xx=g[pre].first+g[u].first+dis[u];
                    int M=dep[u]-(xx/2-g[u].first);
                    if(xx%2==0&&g[u].second>g[pre].second) M++;
                    int y=size[get(u,M)]-size[u];
                    ans[g[u].second]+=y;
                    ans[g[pre].second]+=sum-y;
                }
            }
        }
        for(i=1;i<=tot;i++) ans[g[a[i]].second]+=tmp[a[i]];
    }
     
    int main()
    {
     
        scanf("%d",&n);
        int i;
        for(i=1;i<n;i++)
        {
            int x,y;
            scanf("%d%d",&x,&y);
            gg[x].pb(y);
            gg[y].pb(x);
        }
        DFS(1,0,1);
        int j;
        for(i=1;(1<<i)<=n;i++) for(j=1;j<=n;j++) f[j][i]=f[f[j][i-1]][i-1];
        int Q;
        scanf("%d",&Q);
        while(Q--)
        {
            scanf("%d",&m);
            for(i=1;i<=m;i++)
            {
                a[i]=b[i]=getInt();
                g[a[i]]=MP(0,a[i]);
                ans[a[i]]=0;
            }
            tot=m;
            init();
            cal();
            for(i=1;i<=m;i++)
            {
                printf("%d ",ans[b[i]]);
            }
            puts("");
        }
    }