4044 权力

题面

内容

现在 Y 国在战场有 $n$ 个士兵，编号依次为 $1,2,\dots,n$。$\forall 2\le i\le n$，士兵 $i$ 的直系上司是士兵 $fa_i$。特别的，士兵 $1$ 是指挥官，没有直系上司。保证 $1\le fa_i < i$。

对于士兵 $u,v$ 而言，如果士兵 $v$ 是士兵 $u$ 的直系上司，或者士兵 $fa_u$ 从属于士兵 $v$，则称士兵 $u$ 从属于士兵 $v$。显然，士兵 $u$ 从属于士兵 $v$ 当且仅当存在若干个（假设为 $m$ 个，$m\ge 2$）士兵 $x_1,x_2,\dots,x_m$，其中 $x_1=u,x_m=v$，使得 $\forall 1\le i < m$，士兵 $x_{i+1}$ 是士兵 $x_i$ 的直系上司。

记 $sz_i$ 为从属于士兵 $i$ 的士兵数量，假如 $sz_i\ge {n\over 2}$，那么我们就会称士兵 $i$ 权力很大。

求有多少个士兵权力很大。

输入

第一行一个正整数 $n$。

第二行 $n-1$ 个整数，分别表示 $fa_2,fa_3,\dots,fa_n$。

输出

输出一个数表示答案。

样例1

输入

5
1 1 3 3 

输出

1

样例2

输入

13
1 2 2 1 4 6 7 8 7 10 7 10 

输出

4

提示

对于样例1：士兵 $1$ 权力很大。

对于样例2：士兵 $1,2,4,6$ 权力很大。

思路

DFS。

别忘了减去自己。

除法可能会有精度误差建议用乘法。

代码

#include<bits/stdc++.h>
using namespace std;
const int N=3e5+10;
int n,cnt;
struct edge
{
    int to,nxt;
}e[N<<1];
int fir[N];
void add(int u,int v)
{
    e[++cnt].to=v;
    e[cnt].nxt=fir[u];
    fir[u]=cnt;
}
int sz[N];
bool vis[N];
int dfs(int u)
{
    sz[u]=1,vis[u]=true;
    for(int i=fir[u];i;i=e[i].nxt)
    {
        if(!vis[e[i].to])
        {
            sz[u]+=dfs(e[i].to);
        }
    }
    return sz[u];
}
signed main()
{
    // freopen("E:/下载/Compressed/download/ex_authority4.in","r",stdin);
    scanf("%d",&n);
    for(int i=2;i<=n;i++)
    {
        int fa;
        scanf("%d",&fa);
        add(fa,i);
    }
    dfs(1);
    int ans=0;
    double op=1.0*n/2.0;
    for(int i=1;i<=n;i++)
    {
        if((sz[i]-1)>=op) ans++;
    }
    cout<<ans;
    return 0;
}