HDU 3290 The magic apple tree DFS

The magic apple tree

Time Limit: 3000/1000 MS (Java/Others)    Memory Limit: 65535/32768 K (Java/Others)
Total Submission(s): 842    Accepted Submission(s): 263

Problem Description

Sailormoon girls all like eating many kinds of fruit, such as banana, grape, apple and so on.
One day, when they was walking on a orchard, they found a magic apple tree.The magic apple tree have many nodes,but there is only one root. Each notes has its label. It is labeled from 1.On the first day,only each leaf nodes(has no children nodes) have apples. Any other nodes have no apples. The number of apples that each leaf nodes have is just the label of this node.When all the immediate children of a node each has apples,this node will grow some apple on the next day. If a node has K immediate children node,the number of apple that this node grow on next day is just the number of apples that the (K + 1) / 2th smaller node has.The Xth smaller node means there are X – 1 nodes’ number of apples is less than this node’s number of apple.
Now you task is to calculate the number of apples that the root has at last.

Input

There are multiple test cases.
Each case contains a positive integer N, it means this tree has N nodes, labeled 1, 2, ... N(0 < N <= 20000).
The following N lines describe the children of all nodes in order of their labels. The (X + 1)th line in each test case starts with a number p (0 <= p <N), it means the Xth node has p immediate children nodes.then followed by p positive integer, means the label of immediate child node

Output

Print the number of apples that the root grow at last.

Sample Input

   
   7
2 2 3
2 5 4
2 6 7
0
0
0
0

12
3 2 3 4
0
2 5 6
3 7 8 9
3 10 11 12
0
0
0
0
0
0
0
  
  

Sample Output

   
   4
6
  
  

/*
hdoj 3290 
在一棵苹果树上，有ｎ个节点，
第一天，只有叶节点才有苹果，苹果的数目等于该节点的编号。
第二天开始，其他节点开始长苹果，
对于非叶节点，只有当所有直接子节点都长了苹果之后才开始长，
设它的直接子节点数目总共Ｋ个，
则该节点的苹果数等于所有直接字节点苹果数目中的第(K + 1) / 2大。

问最后根节点的苹果数目。

类似ＤＰ的过程，从根节点开始算，DFS往下搜，再递推回来
每个节点设置ru[i]自己的父节点个数，chu[i]表示自己的子节点个数
map[i][j] 表示第i个节点的第j个子节点 
这里用vector 动态的不然开map数组太大了 
奇怪的是G++ 超时。 但是用C++ 过了 
*/
#include<iostream>
#include<stdio.h>
#include<vector>
#include<algorithm>
using namespace std;

#define MAX 20001
int chu[MAX],ru[MAX];
vector<int> map[MAX]; 

int DFS(int cur){
    
    int i;
    vector<int> f;
    
    if(chu[cur]==0) //是叶子节点 直接返回 
        return cur;
    for(i=0;i<chu[cur];i++)
        f.push_back(DFS(map[cur][i]));//保存每个子节点的苹果数
    
    sort(f.begin(),f.end());
    
    return f[(chu[cur]+1)/2-1];//chu[cur]子节点数 返回第(k+1)/2个 -1是坐标0开始 

}
    
int main(){
    
    int n,i,j,a,root;
    
    //freopen("test.txt","r",stdin);
    
    while(scanf("%d",&n)!=EOF)
    {
        for(i=1;i<=n;i++)
            map[i].clear();
        memset(ru,0,sizeof(ru));
        
        for(i=1;i<=n;i++)
        {
            scanf("%d",&chu[i]);//第i个节点的 子节点个数 
            for(j=0;j<chu[i];j++) 
            {
                scanf("%d",&a);
                map[i].push_back(a);
                ru[a]++;        //a这个节点的父节点+1 
            }
        }
        for(i=1;i<=n;i++)
            if(ru[i]==0)
            {
                root=i;
                break;
            }            
        printf("%d\n",DFS(root));
    }
    return 0;
}