Codeforces 931D Peculiar apple-tree（dfs+思维）.cpp _Codeforces

学向勤中得，萤窗万卷书。这篇文章主要讲述Codeforces 931D Peculiar apple-tree（dfs+思维）.cpp相关的知识，希望能为你提供帮助。
题目链接：http://codeforces.com/contest/931/problem/D
题目大意：给你一颗树，每个节点都会长苹果，然后每一秒钟，苹果往下滚一个。两个两个会抵消苹果。问最后在根节点能收到多少个苹果。
解题思路：昨天是我想复杂了，其实就是统计下每层的苹果数，若是奇数则答案+1。因为最终这些苹果都会滚落汇聚到根节点，所以在滚落过程中肯定会碰撞并相消无论苹果是怎么分布的。
代码：

1 #include< iostream> 2 #include< cstdio> 3 #include< cstring> 4 #include< vector> 5 #include< algorithm> 6 using namespace std; 7 const int N=1e5+5; 8 9 int dep_num[N]; 10 vector< int> v[N]; 11 12 void dfs(int u,int dep){ 13dep_num[dep]++; 14for(int i=0; i< v[u].size(); i++){ 15int t=v[u][i]; 16dfs(t,dep+1); 17} 18 } 19 20 int main(){ 21int n; 22scanf("%d",& n); 23for(int i=2; i< =n; i++){ 24int fa; 25scanf("%d",& fa); 26v[fa].push_back(i); 27} 28dfs(1,1); 29int ans=0; 30for(int i=0; i< N; i++){ 31ans+=dep_num[i]%2; 32} 33printf("%d\n",ans); 34return 0; 35 }

【Codeforces 931D Peculiar apple-tree（dfs+思维）.cpp】