A 暴力操作（opt）
B 异或连通（xor）
C 诡异键盘（keyboard）
D 民主投票（election）
这道题很简单。。。
首先，对于一个节点 \(u\)，如果 \(siz[u]-1\) 大于了其他所有节点能得到的最大值，那么它一定能胜利。
那考虑怎么找到一个值，满足所有节点能得到的最大值最小？用二分答案即可。
对于一次 check，我们需要一个树形 dp 去计算当前节点在最大值为 \(mid\) 下溢出的票数。\(dp[u]+=dp[v]+1\)。
然后，会有三种情况。
-
对于 \(siz[u]>res\)，一定能胜利；
-
对于 \(siz[u]<res\)，一定不能胜利；
-
对于 \(siz[u]=res\)，如果这个点只有一个，那么它可以战胜。否则，若有多个，一定会有几个相等的。那么我们用 \(res-1\) 再跑一个 \(dp\)，如果节点 \(1\) 的值是 \(1\)，就代表有一个节点溢出，并且沿着到根节点的路径一路溢出到根。那只需要再次 dfs，找到那个节点就好了，这个节点一定可以战胜。
然后就是常数问题了。链式前向星的常数小于 vector。
点击查看代码
#include<bits/stdc++.h>
using namespace std;
const int N=1e6+5;
int T,n;
inline int read()
{
register int s=0;
register char c=getchar();
while(c<'0'||c>'9') c=getchar();
while(c>='0'&&c<='9')s=(s<<1)+(s<<3)+(c^48),c=getchar();
return s;
}
void write(int x)
{
if(x>9) write(x/10);
putchar(x%10+'0');
}
struct node{
int to,next;
}e[N<<1];
namespace q{
int *siz,*f;
int head[N],cnt;
inline void add(int u,int v)
{
e[++cnt].to=v,e[cnt].next=head[u];
head[u]=cnt;
}
inline void dfs1(int u)
{
siz[u]=1;
#pragma GCC unroll 2
for(int i=head[u];i;i=e[i].next)
{
int v=e[i].to;
dfs1(v);siz[u]+=siz[v];
// if(siz[v]>siz[Son[u]]) Son[u]=v;
}
}
inline void ddfs(int u,int mx)
{
f[u]=0;
#pragma GCC unroll 2
for(int i=head[u];i;i=e[i].next)
{
int v=e[i].to;
ddfs(v,mx);
f[u]+=f[v]+1;
}
if(f[u]>mx) f[u]-=mx;
else f[u]=0;
}
bitset<N>ans;
bool fdf=0;
inline void dddfs(int u,int V){
if(f[u]&&siz[u]-1==V){
ans[u]=1;
fdf=1;
return ;
}
if(fdf)return ;
#pragma GCC unroll 2
for(int i=head[u];i;i=e[i].next){
int v=e[i].to;
if(fdf)return ;
if(f[v])dddfs(v,V);
}
}
void work()
{
n=read();
f=new int [n+2],siz=new int [n+2];
cnt=0;
#pragma GCC unroll 32
for(int i=1;i<=n;i++)head[i]=0;
#pragma GCC unroll 32
for(int i=2;i<=n;i++)
{
int f=read();
add(f,i);
}
dfs1(1);
int l=1,r=n,res=0;
while(l<=r)
{
int mid=(l+r)>>1;
ddfs(1,mid);
if(f[1]==0) res=mid,r=mid-1;
else l=mid+1;
}
ans.reset();
#pragma GCC unroll 2
for(int i=1;i<=n;i++)
{
if(siz[i]-1>res) ans[i]=1;
}
ddfs(1,res-1);
if(f[1]==1)
{
fdf=0;
dddfs(1,res);
}
for(int i=1;i<=n;i++) write((int)ans[i]);
putchar(10);
delete []siz,delete []f;
}
}
signed main()
{
// freopen("2.in","r",stdin);
// freopen("ans.txt","w",stdout);
freopen("election.in","r",stdin);
freopen("election.out","w",stdout);
T=read();
while(T--) q::work();
return 0;
}