题目里面的注意点还是很多的，如果读错了题整个思路可能会一点都不对。首先是移动和选取硬币的操作是分开的，所以你移动到了一个有硬币的节点，将是你的对手获得硬币。然后移动和拿取都是单次操作的，进行后就换人了。
如果要使总答案最优，那每个节点的决策都要最优。选择了一个节点就要决策完他的整个子树。因此考虑树形DP，我们用儿子来推父亲，当决策一个节点的时候，他的子节点信息我们都已经知道。
设 \(g_i\) 表示点 \(i\) 的子树大小，\(f_i\) 表示在当前节点先手能够得到的最多硬币，那么后手能够得到的最多硬币我们记为 \(h_i = g_i - f_i\)。
模拟几个小数据，假设一个人选择了当前的一个子节点 \(i\) 进入，能够发现当 \(g_i\) 为奇数时，回到 \(i\) 的父亲后变成他的对手进行子节点的选择；当 \(g_i\) 为偶数时，回到 \(i\) 的父亲后仍为他自己选择下一个进入的子节点。
所以一个节点如果有奇数个 \(g\) 为奇数的子节点，最后会交换决策权；偶数个 \(g\) 为奇数的子节点，决策权不变。
我们对子节点的状态分类讨论，均假设为先手拿取了该节点 \(i\) 的硬币，接下来该由后手决策进入哪个子节点 \(j \in son_i\)：
- \(g_j\) 为偶数且 \(f_j < h_j\)，那么对于后手来说这个节点肯定是有利的，因为他能拿得多，还能回来后继续操控局面，所以只要有这类节点，后手必定会选，此类节点的转移方程为 \(f_i = f_i + f_j\)。
- \(g_j\) 为偶数且 \(f_j \le h_j\)，那么对于后手来说这个节点不是亏的就是没有贡献，所以会尽量避免选这类节点，此类节点的转移为 \(f_i = f_i + h_j\)。
- \(g_j\) 为奇数，注意到选择了这类节点后会交换决策权，所以后手会尽量选择优秀的节点——能让他比对手拿得更多的节点，即 \(h_i - f_i\) 尽可能大的节点。
所以整个游戏的流程至此我们能够确定下来了：先拿第一类节点，然后拿第三类节点。判断一下第三类节点总数的奇偶性，看选完第三类节点后会不会交换决策权，从而看第二类节点的贡献到底是给先手还是后手。
整个遍历流程是 \(\mathcal O(n)\) 的复杂度，由于需要我们决策具体哪个第三类节点更优，这里选择使用优先队列，所以总复杂度为 \(\mathcal O(n \log n)\)。
#include<bits/stdc++.h>
#define int long long
#define mp make_pair
using namespace std;
inline int read()
{
int s=0,w=1;
char c=getchar();
while(!isdigit(c)) {if(c=='-') w=-1; c=getchar();}
while(isdigit(c)) s=(s<<1)+(s<<3)+(c^48),c=getchar();
return s*w;
}
bool Mbe;
namespace LgxTpre
{
static const int MAX=100010;
static const int INF=2007070707;
static const int mod=998244353;
int n,x;
struct edge
{
int nex,to;
}e[MAX<<1];
int head[MAX],cnt;
inline void add(int x,int y)
{
e[++cnt].nex=head[x],head[x]=cnt,e[cnt].to=y;
return;
}
#define to e[i].to
int siz[MAX],dp[MAX];
priority_queue<pair<int,int> > q;
void dfs(int now)
{
int tot=0,con=0;
siz[now]=1;
for(int i=head[now];i;i=e[i].nex)
dfs(to),siz[now]+=siz[to],tot^=siz[to]&1;
dp[now]=1;
for(int i=head[now];i;i=e[i].nex)
{
if(siz[to]&1)
q.push(mp(siz[to]-2*dp[to],dp[to]));
else
{
if(dp[to]<siz[to]-dp[to]||(dp[to]>=siz[to]-dp[to]&&(!tot)))
dp[now]+=dp[to];
else
dp[now]+=siz[to]-dp[to];
}
}
while(!q.empty())
{
++con;
auto it=q.top(); q.pop();
if(con&1) dp[now]+=it.second;
else dp[now]+=it.first+it.second;
}
return;
}
#undef to
inline void mian()
{
n=read();
for(int i=2;i<=n;++i)
x=read(),add(x,i);
dfs(1);
printf("%lld",dp[1]);
return;
}
}
bool Med;
signed main()
{
// fprintf(stderr,"%.3lf MB\n",(&Mbe-&Med)/1048576.0);
LgxTpre::mian();
return (0-0);
}