2023NOIP A层联测31 T4 民主投票

思维好题。

思路

首先可以设 \(s\) 每个人最多获得的票数，一开始所有点都把自己的票投给自己父亲。

如果一个点的票数超过 \(s\) 了，那么这个点肯定要把票分给他的父亲。

设 \(f_{u,s}\) 为 \(u\) 点在最多获得 \(s\) 票的情况下要向父亲分的票数（不包括一开始投的）。

如果 \(f_{1,s}\) 大于 \(0\) 表示无法每个点至多获得 \(s\)，反之则可以。

可以二分求这个最小的 \(s\) 值。

点 \(u\) 获得的最多票数是 \(siz_u-1\) 票。

如果 \(siz_u-1>s\) 那么 \(u\) 肯定可以获胜。如果 \(siz_u-1<s\) 那么证明 \(f_{u,s}=0\)，把 \(u\) 子树脱离原树不造成影响，即 \(u\) 子树内所以点投 \(u\) 无法影响最小值 \(s\)，所以 \(siz_u-1<s\) 时，\(u\) 肯定无法获胜。

对于 \(siz_u-1=s\) 而言，\(f_{u,s}=1/0\)。

此时求 \(f_{1,s-1}\)，\(f_{1,s-1}\) 必然大于 \(0\)。

如果 \(f_{1,s-1}=1\)，则这一票肯定是通过某个 \(siz_u-1=s\) 的点传上来，由于点 \(u\) 在被取的情况下不会向上传票，所以点 \(u\) 可以获胜，即去掉 \(u\) 的后代后，\(f_{1,s-1}=0\)。

如果 \(f_{1,s-1}>1\)，肯定是有多个上文分析的点会传票到根，\(u\) 节点不能获胜。

CODE

#include<bits/stdc++.h>
using namespace std;

const int maxn=1e6+5;

struct node
{
    int to,nxt;
}edge[maxn];

int n,tot=0;
int head[maxn],f[maxn],sz[maxn],ans[maxn];

bool fg;

inline void add(int x,int y)
{
    tot++;
    edge[tot].to=y;
    edge[tot].nxt=head[x];
    head[x]=tot;
}

inline void clr()
{
    tot=0;
    for(int i=0;i<=n;i++) head[i]=0,edge[i]={0,0};
}
inline void dfs_sz(int u)
{
    sz[u]=1;
    for(int i=head[u];i;i=edge[i].nxt) dfs_sz(edge[i].to),sz[u]+=sz[edge[i].to];
}
inline void dfs_ans(int u,int mid)
{
    f[u]=0;
    for(int i=head[u];i;i=edge[i].nxt)
    {
        int v=edge[i].to;
        dfs_ans(v,mid);
        f[u]+=f[v]+1;
        if(u==1&&f[u]-mid>0&&fg) return ;
    }
    f[u]=max(0,f[u]-mid);
}
inline void dfs_change(int u,int mid)
{
    if(sz[u]-1==mid){ans[u]=1;return;}
    for(int i=head[u];i;i=edge[i].nxt) if(f[edge[i].to]>0) dfs_change(edge[i].to,mid);
}

int main()
{
    int _;
    scanf("%d",&_);
    while(_--)
    {
        fg=1;
        scanf("%d",&n);
        clr();
        for(int i=2;i<=n;i++)
        {
            int x;
            scanf("%d",&x);
            add(x,i);
        }
        dfs_sz(1);
        int l=1,r=n,x=0;
        while(l<=r)
        {
            int mid=(l+r)>>1;
            dfs_ans(1,mid);
            if(f[1]==0) r=mid-1,x=mid;
            else l=mid+1;
        }
        for(int i=1;i<=n;i++) {ans[i]=(sz[i]-1>x);}
        fg=0;
        dfs_ans(1,x-1);
        if(f[1]==1) dfs_change(1,x);
        for(int i=1;i<=n;i++) printf("%d",ans[i]);
        putchar('\n');
    }
}