# AT2291 题解
题目传送门 AT2291
建议在原 luogu blog 食用更佳！
# 题意简述
通过淘汰赛从 N 个人中选出一个冠军。
# 题目分析
小学的时候学奥数经常遇到这种类似球队比赛。我们小学画的那个树杈图不就是咱们现在的二叉树吗？
所以，我们只需要构造一个树，叶子节点为选手，非叶子节点为该比赛的胜出者，构造出这么一个最优解树。我们给他们编上号，然后开始比赛！
对于冠军一号选手来说，二四六号都要和他打一场，发现这三个人和一号打比赛的顺序变了，比赛的性质就变了啊（直接出现开局就一血）。发现一号要先跟子树高度小的比赛，再跟子树高度大的比赛，因为比赛时间越靠后，这颗子树就越靠近根。然后发现这个可以用递归。
题目给的是一个有根树，如果我们根据最优解树中每个点失败时的深度进行规律的探索，我们就可发现一些东西：
- 若当前根节点的深度为 d，则它的第 i 个儿子的深度为 d+i ，儿子的顺序由子树的高度决定；
- 深度优先搜索
dfs(1) 。
# 代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
| #include<bits/stdc++.h>
using namespace std;
const int M=500005;
int N,Height[M];
vector<int> G[M];
bool cmp(int x,int y)
{
return Height[x]>Height[y];
}
void dfs(int u)
{
for(register int i=0;i<int(G[u].size());i++)
{
dfs(G[u][i]);
}
sort(G[u].begin(),G[u].end(),cmp);
for(register int i=0;i<int(G[u].size());i++)
{
Height[u]=max(Height[u],Height[G[u][i]]+i+1);
}
}
signed main(void)
{
cin>>N;
for(register int i=2;i<=N;i++)
{
int father;
cin>>father;
G[father].push_back(i);
}
dfs(1);
cout<<Height[1]<<endl;
return 0;
}
|
