1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
| #include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <climits>
#include <cassert>
#include <string>
#include <vector>
#include <algorithm>
#include <map>
#include <set>
#include <queue>
#include <sstream>
#include <numeric>
#include <fstream>
#include <iostream>
#include <utility>
#include <iomanip>
#include <stack>
#include <list>
#include <sstream>
#include <vector>
using namespace std;
#define PB push_back
#define MP make_pair
#define REP(i, n) for (int i(0); i < n; ++i)
#define REP1(i, n) for (int i(1); i < n; ++i)
#define REP1N(i, n) for (int i(1); i <= n; ++i)
#define FOR(i, a, b) for (int i(a); i <= b; ++i)
typedef long long ll;
typedef vector<ll> vll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<bool> vb;
typedef vector<vb> vvb;
typedef pair<int, int> pii;
int tc;
int n;
int parentIndex;
struct node {
node() {
child = vector<int>();
}
vector<int> child;
};
node nodes[200001];
pii best1[200001];
pii best2[200001];
bool sort_bests(const pii& left, const pii& right) {
if (left.second == right.second) {
return left.first < right.first;
} else {
return left.second < right.second;
}
}
void solve(int depth, int rootIndex) {
node* root = &nodes[rootIndex];
int csize = root->child.size();
REP(j, csize) {
solve(++depth, root->child[j]);
}
int maxColor = ceil(sqrt(n));
REP1N(rootColor, maxColor) { // find color should be choosen for root
int _res = 0; // subtree sum of root, when picking rootColor
REP(j, csize) { // for each child
int childIndex = root->child[j];
node* child = &nodes[childIndex];
int __res = 0;
if (rootColor == best1[childIndex].first)
__res += best2[childIndex].second;
else
__res += best1[childIndex].second;
_res += __res;
}
_res += rootColor;
pii new_best = MP(rootColor, _res);
if (sort_bests(new_best, best1[rootIndex])) {
best2[rootIndex] = best1[rootIndex];
best1[rootIndex] = new_best;
} else if (sort_bests(new_best, best2[rootIndex])) {
best2[rootIndex] = new_best;
}
}
}
int main(int argc, char* argv[]) {
cin >> tc;
REP(i, tc) {
cin >> n;
REP(j, 200001) {
nodes[j] = node();
best1[j] = MP(INT_MAX, INT_MAX);
best2[j] = MP(INT_MAX, INT_MAX);
}
REP(j, n) {
cin >> parentIndex;
nodes[parentIndex].child.PB(j + 1);
}
solve(1, 1);
int res = best1[1].second > best2[1].second ? best2[1].second : best1[1].second;
cout << res << endl;
}
return 0;
}
|