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');
}
}