This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
namespace std {
template<class Fun>
class y_combinator_result {
Fun fun_;
public:
template<class T>
explicit y_combinator_result(T &&fun): fun_(std::forward<T>(fun)) {}
template<class ...Args>
decltype(auto) operator()(Args &&...args) {
return fun_(std::ref(*this), std::forward<Args>(args)...);
}
};
template<class Fun>
decltype(auto) y_combinator(Fun &&fun) {
return y_combinator_result<std::decay_t<Fun>>(std::forward<Fun>(fun));
}
} // namespace std
struct heavy_light_decomposition {
std::vector<int> par, dep, hed, tin;
heavy_light_decomposition(int R, std::vector<std::vector<int>> T) {
int n = (int)T.size(), time = 0;
par.resize(n), dep.resize(n);
hed.resize(n), tin.resize(n);
par[R] = -1, dep[R] = 0, hed[R] = R;
std::y_combinator([&](auto self, int u) -> int {
int sub = 1, mxs = 0;
for (int &v : T[u]) {
if (v == par[u])
continue;
par[v] = u;
dep[v] = dep[u] + 1;
int t = self(v);
sub += t;
if (mxs < t) {
mxs = t;
std::swap(T[u].front(), v);
}
}
return sub;
})(R);
std::y_combinator([&](auto self, int u) -> void {
tin[u] = time++;
for (int v : T[u]) {
if (v == par[u])
continue;
hed[v] = v == T[u].front() ? hed[u] : v;
self(v);
}
})(R);
}
int lowest_common_ancestor(int u, int v) {
for (; hed[u] != hed[v]; u = par[hed[u]])
if (dep[hed[u]] < dep[hed[v]])
std::swap(u, v);
return dep[u] < dep[v] ? u : v;
}
int distance(int u, int v) { return dep[u] + dep[v] - 2 * dep[lowest_common_ancestor(u, v)]; }
};
class centroid_decomposition {
int n;
std::vector<std::vector<int>> tree;
std::vector<int> parent, weight;
std::vector<bool> block;
int initialize_weight(int u, int p) {
weight[u] = 1;
for (int v : tree[u]) {
if (p == v || block[v])
continue;
weight[u] += initialize_weight(v, u);
}
return weight[u];
}
int find_centroid(int w, int u, int p) {
for (int v : tree[u]) {
if (p == v || block[v])
continue;
if (2 * weight[v] > w)
return find_centroid(w, v, u);
}
return u;
}
void initialize_centroids(int c, int p) {
int w = initialize_weight(c, -1);
c = find_centroid(w, c, -1);
parent[c] = p;
block[c] = true;
for (int v : tree[c]) {
if (block[v])
continue;
initialize_centroids(v, c);
}
}
public:
centroid_decomposition(const std::vector<std::vector<int>> &_tree) : n((int)_tree.size()), tree(_tree) {
parent.resize(n);
weight.resize(n);
block.assign(n, false);
initialize_centroids(0, -1);
}
int operator[](int i) { return parent[i]; }
};
int main() {
using namespace std;
int N, D;
cin >> N >> D;
vector<vector<int>> T(N);
for (int i = 1; i < N; i++) {
int p;
cin >> p;
T[i].push_back(p);
T[p].push_back(i);
}
heavy_light_decomposition hld(0, T);
centroid_decomposition cd(T);
vector<int> ord(N);
iota(ord.begin(), ord.end(), 0);
sort(ord.begin(), ord.end(), [&hld](int a, int b) {
return hld.dep[a] > hld.dep[b];
});
vector<int> ans;
vector<int> dis(N, (int)1e9);
for (int s : ord) {
int cur = (int)1e9;
for (int t = s; t != -1; t = cd[t])
cur = min(cur, dis[t] + hld.distance(s, t));
if (cur >= D) {
ans.push_back(s);
for (int t = s; t != -1; t = cd[t]) {
dis[t] = min(dis[t], hld.distance(s, t));
}
}
}
cout << ans.size() << '\n';
// for (int u : ans)
// cout << u + 1 << ' ';
// cout << '\n';
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |