#include <bits/stdc++.h>
using namespace std;
const int kMaxN = 1e6;
class SemiRing {
public:
SemiRing(int el=0) : el_(el) {}
SemiRing& operator +=(const SemiRing& rhs) {
// u + v = min(u, v);
if (el_ > rhs.el_) {
el_ = rhs.el_;
}
return *this;
}
SemiRing& operator *=(const SemiRing& rhs) {
// u * v = u + v
el_ += rhs.el_;
if (el_ > inf) {
el_ = inf;
}
return *this;
}
SemiRing operator +(const SemiRing& rhs) const { return SemiRing(*this) += rhs; }
SemiRing operator *(const SemiRing& rhs) const { return SemiRing(*this) *= rhs; }
int value() const { return el_; }
public:
static constexpr int inf = 0x3f3f3f3f;
private:
int el_;
};
class Mat22 {
public:
Mat22(SemiRing x00=0, SemiRing x01=SemiRing::inf, SemiRing x10=0, SemiRing x11=SemiRing::inf)
: a00(x00), a01(x01), a10(x10), a11(x11) {}
Mat22 operator *=(const Mat22& rhs) {
return *this = *this * rhs;
}
Mat22 operator *(const Mat22& rhs) const {
// Normal matrix multiplication.
return Mat22(
a00 * rhs.a00 + a01 * rhs.a10,
a00 * rhs.a01 + a01 * rhs.a11,
a10 * rhs.a00 + a11 * rhs.a10,
a10 * rhs.a01 + a11 * rhs.a11);
}
int Get00() const { return a00.value(); }
int Get01() const { return a01.value(); }
int Get10() const { return a10.value(); }
int Get11() const { return a11.value(); }
friend ostream& operator <<(ostream& os, const Mat22& rhs) {
os << "{ { " << rhs.a00.value() << " " << rhs.a01.value() << " }, ";
os << "{ " << rhs.a10.value() << " " << rhs.a11.value() << " } }";
return os;
}
private:
SemiRing a00, a01, a10, a11;
};
int n;
int next_idx;
vector<int> graph[kMaxN];
int weight[kMaxN], parent[kMaxN], head[kMaxN], bottom[kMaxN], vid[kMaxN];
Mat22 tree[2 * kMaxN], light_value[kMaxN];
int last_skip[kMaxN], last_take[kMaxN];
int GetId(int l, int r) {
return (l + r) | (l != r);
}
// Range query: Product of. matrices.
Mat22 Query(int l, int r, int q_l, int q_r) {
int id = GetId(l, r);
if (q_l <= l and r <= q_r) {
return tree[id];
} else {
int m = (l + r) / 2;
if (q_r <= m) {
return Query(l, m, q_l, q_r);
} else if (q_l > m) {
return Query(m + 1, r, q_l, q_r);
} else {
return Query(l, m, q_l, q_r) * Query(m + 1, r, q_l, q_r);
}
}
}
// Initialise segment tree.
void BuildTree(int l, int r) {
int id = GetId(l, r);
if (l == r) {
tree[id] = light_value[l];
} else {
int m = (l + r) / 2;
BuildTree(l, m);
BuildTree(m + 1, r);
tree[id] = tree[GetId(l, m)] * tree[GetId(m + 1, r)];
}
}
// Point update: Update the leaf value for a node.
void Update(int l, int r, int pos) {
int id = GetId(l, r);
if (l == r) {
tree[id] = light_value[l];
} else {
int m = (l + r) / 2;
if (pos <= m) {
Update(l, m, pos);
} else {
Update(m + 1, r, pos);
}
tree[id] = tree[GetId(l, m)] * tree[GetId(m + 1, r)];
}
}
Mat22 PathValue(int node) {
// {{a b} {c d}} * {{0 inf} {0 inf}} = {{min(a, b) inf} {min(c, d) inf}}
// try attaching a dummy empty heavy node: {{0 inf} {0 inf}}
// as we always added a light leaf in the path.
return Query(0, n - 1, vid[head[node]], bottom[head[node]]) * Mat22(0, SemiRing::inf, 0, SemiRing::inf);
}
void LightLeaf(int node) {
// append the leaf node to the end of HLD path till now.
bottom[head[node]] = vid[node];
// Traverse till you reach the HLD path containing root i.e. 1.
while (parent[head[node]] != -1) {
// Update the HLD path containing node. This is characterised by
// head[node].
node = head[node];
// Find product of matrices in the HLD path.
auto val = PathValue(node);
// Find the parent_idx for updating its matrix later.
// Refer to example matrices in editorial to understand how the calculations
// look like.
int parent_idx = vid[parent[node]];
int add_skip = val.Get00() - last_skip[node];
int add_take = val.Get10() - last_take[node];
int parent_skip = light_value[parent_idx].Get00() + add_skip - 1;
int parent_take = light_value[parent_idx].Get01() + add_take;
// Similar to solution for 41 points, persist the value for the changes we
// did to this chain till now.
last_skip[node] += add_skip;
last_take[node] += add_take;
// General Matrix is {{1 + g(u), f(u)} {1 + g(u), inf}}
// where f(u) means "u" is definitely taken.
light_value[parent_idx] = Mat22(parent_skip + 1, parent_take, parent_skip + 1, SemiRing::inf);
// Update the matrix for the parent as a new child was added.
Update(0, n - 1, parent_idx);
// Change the chain.
node = parent[node];
}
}
// Subtree sum.
void FindWeights(int node) {
weight[node] = 1;
for (auto&& son : graph[node]) {
FindWeights(son);
weight[node] += weight[son];
}
}
// HLD decomposition.
// vid[node] = position in HLD array
// head[node] = node from which HLD path containing "node" begins.
// There are 2 ways to decompose.
// 1. Either based on the largest subtree.
// 2. Or decompose every subtree expect the one containing atleast half of the
// nodes.
void Decompose(int node, int path_head) {
vid[node] = next_idx++; head[node] = path_head;
for (auto&& son : graph[node]) {
if (weight[node] < 2 * weight[son]) {
// Heavy-child
Decompose(son, path_head);
}
}
for (auto&& son : graph[node]) {
if (weight[node] >= 2 * weight[son]) {
// Light-child, start a new chain.
Decompose(son, son);
}
}
}
int BoatSize(int num_nodes, int mvc) {
if (num_nodes <= 3) {
// base case.
return 2;
}
if (mvc == 1) {
// Special case: star graph.
return 3;
}
// include chef in minimum vertex cover.
return 1 + mvc;
}
int main() {
cin.tie(0);
ios_base::sync_with_stdio(false);
int num_tests; cin >> num_tests;
while (num_tests--> 0) {
// O-based indexing is used in the solution.
// Input.
cin >> n;
parent[0] = -1;
for (int i = 1; i < n; ++i) {
cin >> parent[i]; --parent[i];
graph[parent[i]].push_back(i);
}
// Subtree sum.
FindWeights(0);
// HLD decompostion.
Decompose(0, 0);
// Base values for leaves.
for (int i = 0; i < n; ++i) {
// Unity matrix as discussed in editorial.
light_value[i] = Mat22(1, 0, 1, SemiRing::inf);
}
// Initialise Segment tree.
BuildTree(0, n - 1);
// Insert root node 1.
LightLeaf(0);
for (int i = 1; i < n; ++i) {
// Insert leaves one by one.
LightLeaf(i);
cout << BoatSize(i + 1, PathValue(0).Get00()) << " \n"[i == n - 1];
}
// Clear.
next_idx = 0;
for (int i = 0; i < n; ++i) {
graph[i].clear();
last_skip[i] = 0;
last_take[i] = 0;
}
}
}