#line 1 "test/library-checker/Tree/FrequencyTableOfTreeDistance.test.cpp"
#define PROBLEM \
"https://judge.yosupo.jp/problem/frequency_table_of_tree_distance"
#include <bits/stdc++.h>
#include <atcoder/convolution>
using namespace atcoder;
#line 1 "library/tree/CentroidDecomposition.hpp"
template <typename TREE> class CentroidDecomposition {
TREE T;
std::vector<int> sz, pre, timing;
int find_centroid(int v) {
std::vector<int> S{v};
pre[v] = -1;
for (int i = 0; i < S.size(); i++) {
const int u = S[i];
sz[u] = 1;
for (int to : T[u]) {
if (to == pre[u] || ~timing[to])
continue;
pre[to] = u;
S.push_back(to);
}
}
int SZ = S.size();
std::ranges::reverse(S);
for (int u : S) {
if (SZ - sz[u] <= SZ / 2)
return u;
sz[pre[u]] += sz[u];
}
assert(false);
return -1;
};
public:
std::vector<int> order;
CentroidDecomposition(TREE T) : T(T), sz(T.n), pre(T.n), timing(T.n, -1) {
order.reserve(T.n);
std::queue<int> que;
que.push(0);
while (que.size()) {
int c = find_centroid(que.front());
que.pop();
timing[c] = order.size();
order.push_back(c);
for (int to : T[c])
if (timing[to] < 0)
que.push(to);
}
}
template <typename X, typename F, typename G, typename H>
void calc(int root, X initial_val, const F &next_val, const G &action,
const H &finish) {
std::queue<std::tuple<int, int, X>> que;
auto f = [&](int v_, int pre_, X val_, bool is_all) {
que.emplace(v_, pre_, val_);
while (que.size()) {
auto [v, pre, val] = que.front();
que.pop();
action(val, is_all);
for (const auto &e : T[v]) {
if (e.to == pre || timing[e.to] <= timing[root])
continue;
que.emplace(e.to, v, next_val(val, e));
}
}
finish(is_all);
};
for (const auto &e : T[root])
if (timing[e.to] > timing[root])
f(e.to, root, next_val(initial_val, e), false);
f(root, -1, initial_val, true);
}
template <typename X, typename F, typename G, typename H>
void all_calc(X initial_val, const F &next_val, const G &action,
const H &finish) {
for (int i = 0; i < T.n; i++)
calc(i, initial_val, next_val, action, finish);
}
};
#line 2 "library/graph/Graph.hpp"
#line 6 "library/graph/Graph.hpp"
struct Edge {
int from, to;
Edge() = default;
Edge(int from, int to) : from(from), to(to) {}
operator int() const { return to; }
};
struct Graph {
int n;
using edge_type = Edge;
std::vector<edge_type> edges;
protected:
std::vector<int> in_deg;
bool prepared;
class OutgoingEdges {
Graph *g;
int l, r;
public:
OutgoingEdges(Graph *g, int l, int r) : g(g), l(l), r(r) {}
edge_type *begin() { return &(g->edges[l]); }
edge_type *end() { return &(g->edges[r]); }
edge_type &operator[](int i) { return g->edges[l + i]; }
int size() const { return r - l; }
};
class ConstOutgoingEdges {
const Graph *g;
int l, r;
public:
ConstOutgoingEdges(const Graph *g, int l, int r) : g(g), l(l), r(r) {}
const edge_type *begin() const { return &(g->edges[l]); }
const edge_type *end() const { return &(g->edges[r]); }
const edge_type &operator[](int i) const { return g->edges[l + i]; }
int size() const { return r - l; }
};
public:
OutgoingEdges operator[](int v) {
assert(prepared);
return {this, in_deg[v], in_deg[v + 1]};
}
const ConstOutgoingEdges operator[](int v) const {
assert(prepared);
return {this, in_deg[v], in_deg[v + 1]};
}
bool is_prepared() const { return prepared; }
Graph() : n(0), in_deg(1, 0), prepared(false) {}
Graph(int n) : n(n), in_deg(n + 1, 0), prepared(false) {}
Graph(int n, int m, bool directed = false, int indexed = 1)
: n(n), in_deg(n + 1, 0), prepared(false) {
scan(m, directed, indexed);
}
void resize(int n) { n = n; }
void add_arc(int from, int to) {
assert(!prepared);
assert(0 <= from and from < n and 0 <= to and to < n);
edges.emplace_back(from, to);
in_deg[from + 1]++;
}
void add_edge(int u, int v) {
add_arc(u, v);
add_arc(v, u);
}
void add_arc(const edge_type &e) { add_arc(e.from, e.to); }
void add_edge(const edge_type &e) { add_edge(e.from, e.to); }
void scan(int m, bool directed = false, int indexed = 1) {
edges.reserve(directed ? m : 2 * m);
while (m--) {
int u, v;
std::cin >> u >> v;
u -= indexed;
v -= indexed;
if (directed)
add_arc(u, v);
else
add_edge(u, v);
}
build();
}
void build() {
assert(!prepared);
prepared = true;
for (int v = 0; v < n; v++)
in_deg[v + 1] += in_deg[v];
std::vector<edge_type> new_edges(in_deg.back());
auto counter = in_deg;
for (auto &&e : edges)
new_edges[counter[e.from]++] = e;
edges = new_edges;
}
void graph_debug() const {
#ifndef __LOCAL
return;
#endif
assert(prepared);
for (int from = 0; from < n; from++) {
std::cerr << from << ";";
for (int i = in_deg[from]; i < in_deg[from + 1]; i++)
std::cerr << edges[i].to << " ";
std::cerr << "\n";
}
}
};
#line 3 "library/tree/Tree.hpp"
struct Tree : Graph {
using Graph::Graph;
Tree() = default;
int root = -1;
std::vector<int> DFS, BFS, depth;
void scan_root(int indexed = 1) {
for (int i = 1; i < n; i++) {
int p;
std::cin >> p;
add_edge(p - indexed, i);
}
build();
}
void scan(int indexed = 1) {
Graph::scan(n - 1, false, indexed);
build();
}
edge_type &parent(int v) {
assert(~root and root != v);
return (*this)[v][0];
}
const edge_type &parent(int v) const {
assert(~root and root != v);
return (*this)[v][0];
}
OutgoingEdges son(int v) {
assert(~root);
if (v == root)
return {this, in_deg[v], in_deg[v + 1]};
return {this, in_deg[v] + 1, in_deg[v + 1]};
}
private:
void dfs(int v, int pre = -1) {
for (auto &e : (*this)[v]) {
if (e.to == pre)
std::swap((*this)[v][0], e);
else {
depth[e.to] = depth[v] + 1;
dfs(e.to, v);
}
}
DFS.push_back(v);
}
public:
void build(int r = 0) {
if (!is_prepared())
Graph::build();
if (~root) {
assert(r == root);
return;
}
root = r;
depth = std::vector<int>(n, 0);
DFS.reserve(n);
BFS.reserve(n);
dfs(root);
std::queue<int> que;
que.push(root);
while (que.size()) {
int p = que.front();
que.pop();
BFS.push_back(p);
for (const auto &e : son(p))
que.push(e.to);
}
}
};
#line 10 "test/library-checker/Tree/FrequencyTableOfTreeDistance.test.cpp"
using ll = long long;
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
int n;
std::cin >> n;
Tree T(n);
T.scan(0);
CentroidDecomposition CD(T);
std::vector<ll> ans(n, 0), D{0};
auto next_val = [&](int d, auto &e) { return d + 1; };
auto action = [&](int d, bool add) {
if (D.size() <= d)
D.push_back(0);
D[d]++;
};
auto finish = [&](bool add) {
auto D2 = convolution_ll(D, D);
for (int i = 0; i < D2.size() and i < n; i++)
if (add)
ans[i] += D2[i];
else
ans[i] -= D2[i];
D = std::vector<ll>{0};
};
CD.all_calc(0, next_val, action, finish);
for (int i = 1; i < n; i++)
std::cout << ans[i] / 2 << "\n "[i + 1 < n];
}
test/library-checker/Tree/FrequencyTableOfTreeDistance.test.cpp
build/pch/stdc++.hpp