http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=5337
1 #include <cstdio> 2 #include <cstring> 3 #include <vector> 4 #include <algorithm> 5 using namespace std; 6 7 vector<int>g[1001100]; 8 int a[100101]; 9 int in[100101]; 10 int n; 11 int dfs(int u) 12 { 13 int c,x; 14 if(in[u]==0) return 1; 15 if(in[u]==1) 16 { 17 c=dfs(g[u][0]); 18 return c; 19 } 20 else 21 { 22 c=dfs(g[u][0]); 23 x=dfs(g[u][1]); 24 if(c!=x) return max(x,c); 25 else return c+1; 26 } 27 28 } 29 30 int main() 31 { 32 while(scanf("%d",&n)!=EOF) 33 { 34 for(int i=1; i<=n; i++) 35 { 36 g[i].clear(); 37 } 38 memset(in,0,sizeof(in)); 39 for(int i=1; i<=n-1; i++) 40 { 41 scanf("%d",&a[i]); 42 g[a[i]].push_back(i+1); 43 in[a[i]]++; 44 } 45 printf("%d ",dfs(1)); 46 } 47 return 0; 48 }