AtCoder Grand Contest 009—Tournament

题目描述
N contestants participated in a competition. The total of N−1
matches were played in a knockout tournament. For some reasons, the
tournament may not be “fair” for all the contestants. That is, the
number of the matches that must be played in order to win the
championship may be different for each contestant. The structure of
the tournament is formally described at the end of this statement.

After each match, there were always one winner and one loser. The last
contestant standing was declared the champion.

For convenience, the contestants were numbered 1 through N. The
contestant numbered 1 was the champion, and the contestant numbered
i(2≤i≤N) was defeated in a match against the contestant numbered ai.

We will define the depth of the tournament as the maximum number of
the matches that must be played in order to win the championship over
all the contestants.

Find the minimum possible depth of the tournament.

The formal description of the structure of the tournament is as
follows. In the i-th match, one of the following played against each
other:

Two predetermined contestants One predetermined contestant and the
winner of the j-th match, where j(j

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int visit[101010],child[101010],f[101010];
struct point{
    int st,x,fa,deep;
    friend bool operator<(point a,point b){//<左边的后出，<右边的先出
        if(a.st==b.st) return a.deep<b.deep;
        return a.st>b.st;
    }
}e[101010];
vector<int> G[101010];
priority_queue<point>q;
void dfs(int x,int deep){
    if(visit[x]==1) return;
    visit[x]=1;
    e[x].x=x;e[x].fa=f[x];e[x].deep=deep;
    e[x].st=0;
    if(child[x]==0){
        q.push(e[x]);
    }
    for(int i=0;i<G[x].size();i++){
        dfs(G[x][i],deep+1);
    }
}
int main()
{
    int n;cin>>n;
    for(int i=2;i<=n;i++){
        scanf("%d",&f[i]);
        child[f[i]]++;//f[i]的孩子数量
        G[f[i]].push_back(i);
    }
    f[1]=1;//1的父亲是他自己
    dfs(1,0);
    while(!q.empty()){
        point u=q.top();q.pop();
        if(u.x==1) break;
        e[u.fa].st=max(e[u.fa].st,e[u.x].st)+1;
        child[u.fa]--;
        if(child[u.fa]==0)
            q.push(e[u.fa]);
    }
    int ans=0;
    for(int i=1;i<=n;i++)
        ans=max(ans,e[i].st);
    printf("%d\n",ans);
    return 0;
}