【AtCoder】AGC009 Tournament
题目
题目大意
现在需要通过场淘汰赛从个人中选出一个冠军(记为号),如图所示,由于每个人进行的比赛数可能不同,所以这个比赛是不太公平的。现在告诉你每个人个人最终分别被谁打败了(除了冠军号),你需要使整个比赛尽可能公平,即:使(理论上)打比赛最多的人打的比赛尽量少,简单来说,就是使你构造出的这个比赛的树深度尽量小,问它的深度。
(号要打场比赛,号要打场比赛,号理论上要打场比赛)
在这个图中,号最终被号打败了,号被号打败了。
思路
这是一道分的B题。
先给出样例二的构造方法(叶子节点为选手,非叶子节点为该比赛的胜出者),记这个叫最优解树:链剖??
对于冠军号选手来说,都要和他打一场,发现这三个人和号打比赛的顺序变了,比赛的“公平性”就会有所变化,例如:
号:我这是造了什么孽啊= =
发现号要先跟子树高度小的(如)比赛,再跟子树高度大的(如)比赛,因为比赛时间越靠后,这颗子树就越靠近根。
这个性质是可以递归的,但是这个样例不好体现。假设在这个样例的基础上,还要和号打一场,且号胜,那么号就要先和打,再和打,因为的子树高度为,而没有子树。
怎么实现?
题目给出的实际上是一个有根树,如果我们把最优解树中每个点失败时的深度标在这个图上(样例二):
俗话说得好,玩信竞怎么能没有找规律的能力。
于是就找到了规律:
这个树的形态只能是这样,改变儿子的顺序都行。
注意加粗的深度和高度,都是表示在最优解树中的深度和高度,其他的描述都是在给出的树种定义的,我们需要在给出的树中“想象”出这个最优解树。
- 若当前根节点的深度为,则它的第个儿子的深度为,儿子的顺序由这个子树的高度决定。
- 根据根节点的深度(深度)为,递归。
(其实证明很简单)
上面这段话可能不太好理解,最好是你按照自己找到的规律写递归。
代码
发现代码很短 (这道题其实是结论题)
#include<cstdio>
#include<vector>
#include<algorithm>
using namespace std;
#define MAXN 100000
int N;
int Height[MAXN+5];
vector<int> G[MAXN+5];
bool cmp(int x,int y){
return Height[x]>Height[y];
}
//深度从0开始比较方便
void dfs(int u){
for(int i=0;i<int(G[u].size());i++)
dfs(G[u][i]);//得到子树的高度
sort(G[u].begin(),G[u].end(),cmp);//对儿子排序(注意上面的cmp)
for(int i=0;i<int(G[u].size());i++)
Height[u]=max(Height[u],Height[G[u][i]]+i+1);//更新自己这个子树的高度
}
int main(){
scanf("%d",&N);
for(int i=2;i<=N;i++){
int fa;
scanf("%d",&fa);
G[fa].push_back(i);
}
dfs(1);
printf("%d",Height[1]);
}