Peculiar apple-tree
传送门
题意:有一颗树，树上有n多花，都已经结果并按照一定规则掉落，把它们从1~n进行标号，只有当苹果掉到1时才能采摘。当偶数个掉到同一朵花上时，它们消失不见，如果是奇数则剩下一个。它们掉落的规则由一个大小为n-1的序列确定——–i花上的苹果掉到pi花上。保证它们的终点都为1；
思路:掉落的轨迹可以看出它是一棵树，并且只有同深度的苹果才能互相影响到，我们按照父节点的不同把同一深度的节点分组，每一组不是奇数就是偶数(废话)，这样我们可以看出偶数组对答案的贡献值只有0，并且不会对父节点之后的点产生影响，所以忽略偶数组，而奇数组是否对答案有贡献则取决于有多少组奇数组，奇数加奇数等于偶数，所以当有奇数个奇数组(该深度有奇数个苹果)时对答案的贡献为1，否则为0.
#include <iostream>
#include <fstream>
#include <cstdio>
#include <cstring>
#include <queue>
#include <stack>
#include <vector>
#include <map>
#include <set>
#include <cmath>
#include <algorithm>
#include <functional>
#define inf 10000000
using namespace std;
typedef long long ll;
const int MAXN=
1e9+
10;
const int MAX=
1e5+
10;
const double eps=
1e-6;
int n;
int s[MAX];
int depth[MAX];
vector<int>G[MAX];
void dfs(
int node,
int t){
depth[t+
1]+=G[node].size();
for(
int i=
0;i<G[node].size();i++){
int v=G[node][i];
dfs(v,t+
1);
}
}
int main(){
#ifdef ONLINE_JUDGE
#else
freopen(
"in.txt",
"r",stdin);
#endif
cin>>n;
for(
int i=
2;i<=n;i++)
scanf(
"%d",&s[i]);
for(
int i=
2;i<=n;i++)
G[s[i]].push_back(i);
int ans=
1;
dfs(
1,
1);
for(
int i=
2;i<=n;i++)
ans+=depth[i]%
2;
cout<<ans<<endl;
return 0;
}
