链接：https://ac.nowcoder.com/acm/contest/3005/F
来源：牛客网

题目描述

现有一个 n 个点，n-1条边组成的树，其中 1 号点为根节点。
牛牛和牛妹在树上玩游戏，他们在游戏开始时分别在树上两个不同的节点上。
在游戏的每一轮，牛牛先走一步，而后 牛妹走一步。他们只能走到没有人的空节点上。如果谁移动不了，就输掉了游戏。现在牛牛和牛妹决定随机选择他们分别的起点，于是他们想知道，有多少种游戏开始的方式，使得牛牛存在一种一定获胜的最优策略。
两种开始方式相同，当且仅当在两种开始方式中 牛牛，牛妹的开始位置是分别相同的，否则开始方式就被视作不同的。

输入描述:

第一行输入为一个整数 n，代表树的点数。
第二行n-1个整数 p2,p3,…,pnp_2,p_3,\ldots,p_{n}p2​,p3​,…,pn​，分别代表2,3,...,n号点的父节点编号。

输出描述:

一行一个整数，代表答案。
示例1

输入

复制 
3
1 2

输出

复制 
2

说明

当且仅当牛牛在1号点，牛妹在3号点，或者牛牛在3号点，牛妹在1号点时，牛牛才获胜。
示例2

输入

复制 
2
1

输出

复制 
0

说明

由于无论如何牛牛都无路可走，因此必然牛妹获胜。
示例3

输入

复制 
30
1 1 2 1 2 1 3 2 3 4 2 3 1 2 3 4 2 4 5 6 3 4 12 12 12 13 13 13 13

输出

复制 
4

说明

QwQ

备注:

n≤106n \le 10^6n≤106
1≤pi<i1\le p_i < i1≤pi​<i


思路
　　通过画图不难发现只有相隔偶数步时为必胜态，对于每条树链进行间隔点染色，统计不同颜色的点。
　　答案就是两种颜色的点的数量*（数量-1）相加
CODE
 1 #include <bits/stdc++.h>
 2 #define dbg(x) cout << #x << "=" << x << endl
 3 
 4 using namespace std;
 5 typedef long long LL;
 6 
 7 template<class T>inline void read(T &res)
 8 {
 9     char c;T flag=1;
10     while((c=getchar())<'0'||c>'9')if(c=='-')flag=-1;res=c-'0';
11     while((c=getchar())>='0'&&c<='9')res=res*10+c-'0';res*=flag;
12 }
13 
14 namespace _buff {
15     const size_t BUFF = 1 << 19;
16     char ibuf[BUFF], *ib = ibuf, *ie = ibuf;
17     char getc() {
18         if (ib == ie) {
19             ib = ibuf;
20             ie = ibuf + fread(ibuf, 1, BUFF, stdin);
21         }
22         return ib == ie ? -1 : *ib++;
23     }
24 }
25 
26 int qread() {
27     using namespace _buff;
28     int ret = 0;
29     bool pos = true;
30     char c = getc();
31     for (; (c < '0' || c > '9') && c != '-'; c = getc()) {
32         assert(~c);
33     }
34     if (c == '-') {
35         pos = false;
36         c = getc();
37     }
38     for (; c >= '0' && c <= '9'; c = getc()) {
39         ret = (ret << 3) + (ret << 1) + (c ^ 48);
40     }
41     return pos ? ret : -ret;
42 }
43 
44 const int maxn = 1e6 + 7;
45 LL ans = 0;
46 LL cnt1 = 1;
47 LL cnt0 = 0;
48 
49 int cnt = 0;
50 int color[maxn];
51 int head[maxn << 1],nxt[maxn << 1];
52 
53 int edge[maxn << 1];
54 
55 void add(int a, int b) {
56     edge[cnt] = b;
57     nxt[cnt] = head[a];
58     head[a] = cnt++;
59 }
60 
61 void dfs(int u) {
62     //dbg(u),dbg(cnt1),dbg(cnt0);
63 
64     for(int i = head[u]; ~i; i = nxt[i]) {
65         int v = edge[i];
66         //dbg(v);
67         if(v == u) continue;
68         color[v] = !color[u];
69         if(color[v] == 1) cnt1++;
70         if(color[v] == 0) cnt0++;
71         dfs(v);
72     }
73 }
74 
75 int main()
76 {
77     memset(color,0,sizeof(color));
78     int n;
79     read(n);
80     ans = 0;
81     memset(head,-1,sizeof(head));
82     for(int i = 2, x; i <= n; ++i) {
83         read(x);
84         add(x,i);
85     }
86 
87     cnt1 = 1;
88     color[1] = 1;
89     dfs(1);
90     if(cnt1 < 2 && cnt0 < 2) {
91         printf("0\n");
92         return 0;
93     }
94     cout << cnt1*(cnt1-1) + cnt0*(cnt0-1) << endl;
95     return 0;
96 }
View Code