【agc009b】Tournament

Description

一场锦标赛有n个人，总共举办n-1次比赛，每次比赛必定一赢一输，输者不能再参赛。也就是整个锦标赛呈一个二叉树形式。已知一号选手是最后的胜者，以及对于i号选手（i＞1）都知道他是被编号为ai的选手击败的。求这棵二叉树的最小可能深度。

Solution

若一场比赛为一个树上的节点，可以发现，同一位选手的比赛必为一条链（深度递增）。

记录每位选手i击败的选手个数为sum，编号a[i][j]（0＜j≤sum），记以该选手i最后一场比赛（即离根节点最近的点）为根的子树的最小深度为dis[i]。

当sum=0时，$dis[i]=0$；

当sum＞0时，将a[i][1]到a[i][sum]按dis值从大到小排，$dis[i]=\sum\limits_{j=1}^{sum}{min\{i+dis[a[i][j]]\}}$；

dfs一次即可，dis[1]即为答案。

Code

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 using namespace std;

 #define next _next

 struct edge{

     int to,next;

 }e[];

 int n,f[]={},a[],head[];

 bool cmp(int a,int b){

     return a>b;

 }

 void dfs(int u){

     int sum=,minn=;

     for(int i=head[u];~i;i=e[i].next)

         dfs(e[i].to);

     for(int i=head[u];~i;i=e[i].next)

         a[++sum]=f[e[i].to];

     if(sum==)

         return;

     sort(a+,a+sum+,cmp);

     for(int i=;i<=sum;i++)

         minn=max(minn,i+a[i]);

     f[u]=minn;

     return;

 }

 int main(){

     memset(head,-,sizeof(head));

     scanf("%d",&n);

     for(int i=,x;i<=n;i++){

         scanf("%d",&x);

         e[i]=(edge){i,head[x]};

         head[x]=i;

     }

     dfs();

     printf("%d\n",f[]);

     return ;

 }

巴特西

【agc009b】Tournament

Description

Solution

Code

最新文章

热门文章