树上博弈

树上博弈
https://ac.nowcoder.com/acm/contest/3005/F


首先，注意到输掉的唯一方法是自己的唯一一条边有另一个人，那么自己一定是在叶子上。
令两个人之间的距离为D。请注意，每人行动后D增加1或减少1。 因此，每有人走一步D的奇偶性都会改变。
假设最初，在牛牛移动之前，D是偶数。 那么当牛牛移动时D将始终为偶数，而当牛妹移动时D将始终为奇数。
请注意，只要牛牛和牛妹的令牌位于相邻的节点中，D=1。因此，如果D为偶数，则他们不在相邻的单元格中，并且牛牛始终可以移动。
另一方面，由于牛牛总是可以移动，因此他可以向牛妹的方向移动，将牛妹必然会最终移动到叶子上。同样，如果最初D是奇数，则牛妹获胜。
因此，答案取决于距离的奇偶性：如果是偶数，则牛牛获胜，否则牛妹获胜。
可以发现，只有牛牛的初始位置和牛妹的初始位置距离为偶数时，牛牛获胜。只需要分别求出深度为奇数的点和深度为偶数的点的数量即可。
cnt 为 ll

#pragma warning (disable :4996)
#include <iostream>
#include <cstdio>
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod = 1e9 + 7;
const int N = 1e6 + 10;

int n;
int Depth[N];
ll cnt[2];
int main() {
    scanf("%d", &n);
    Depth[1] = 0;
    cnt[0] = 1;
    for (int i = 2; i <= n; i++) {
        int c;
        scanf("%d", &c);

        Depth[i] = Depth[c] + 1;
        cnt[Depth[i] & 1]++;
    }
    cout << cnt[0] * (cnt[0] - 1) + cnt[1] * (cnt[1] - 1) << endl;
}