#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>
#include <cassert>
#include <array>
#include <numeric>
#include <set>
#include <queue>
using namespace std;
using ll = long long;
#define pb push_back
template<typename T, typename = void> struct is_iterable : false_type {};
template<typename T> struct is_iterable<T, void_t<decltype(begin(declval<T>())),decltype(end(declval<T>()))>> : true_type {};
template<typename T> typename enable_if<is_iterable<T>::value&&!is_same<T, string>::value,ostream&>::type operator<<(ostream &cout, T const &v);
template<typename A, typename B> ostream& operator<<(ostream &cout, pair<A, B> const &p) { return cout << "(" << p.f << ", " << p.s << ")"; }
template<typename T> typename enable_if<is_iterable<T>::value&&!is_same<T, string>::value,ostream&>::type operator<<(ostream &cout, T const &v) {
cout << "[";
for (auto it = v.begin(); it != v.end();) {
cout << *it;
if (++it != v.end()) cout << ", ";
}
return cout << "]";
}
void dbg_out() { cout << endl; }
template<typename Head, typename... Tail> void dbg_out(Head H, Tail... T) { cout << ' ' << H; dbg_out(T...); }
#ifdef LOCAL
#define debug(...) cout << "(" << #__VA_ARGS__ << "):", dbg_out(__VA_ARGS__)
#else
#define debug(...) "zzz"
#endif
#define all(x) x.begin(),x.end()
#define F0R(i,n) for (int i = 0; i < n; i++)
//benq
constexpr ll INF = 1e9;
struct Lazy {
ll app, x;
Lazy(ll a, ll b) : app(a), x(b) {}
Lazy() : app(INF), x(-INF) {}
Lazy& operator+=(const Lazy& o) {
this->app = min(this->app, o.app);
this->x = max(this->x, o.x);
return *this;
}
};
struct Info {
ll max_depth, min_active;
Info() : max_depth(-INF), min_active(INF) {}
Info(ll md, ll ma) : max_depth(md), min_active(ma) {}
friend Info operator+(const Info& a, const Info& b) {
Info ret;
ll val_1 = a.min_active - 2LL * a.max_depth;
ll val_2 = b.min_active - 2LL * b.max_depth;
if (val_1 < val_2) return a;
else return b;
}
Info& operator+=(const Lazy& o) {
this->max_depth = max(this->max_depth, o.x);
this->min_active = min(this->min_active, o.app);
return *this;
}
};
template<class T, int SZ, class Lazy> struct LazySeg {
//zero indexed
static_assert(__builtin_popcount(SZ) == 1); // SZ must be power of 2
const T ID{}; T cmb(const T& a, const T& b) { return a+b; }
T seg[2*SZ];
Lazy lazy[2*SZ];
LazySeg() { F0R(i,2*SZ) seg[i] = {}, lazy[i] = {}; }
void push(int ind, int L, int R) { /// modify values for current node
seg[ind] += lazy[ind]; // dependent on operation
if (L != R) F0R(i,2) lazy[2*ind+i] += lazy[ind]; /// prop to children
lazy[ind] = {};
} // recalc values for current node
void pull(int ind){seg[ind]=cmb(seg[2*ind],seg[2*ind+1]);}
void build() { for (int i = SZ - 1; i >= 1; --i) pull(i); }
void upd(int lo,int hi,const Lazy& inc,int ind=1,int L=0, int R=SZ-1) {
push(ind,L,R); if (hi < L || R < lo) return;
if (lo <= L && R <= hi) {
lazy[ind] += inc; push(ind,L,R); return; }
int M = (L+R)/2; upd(lo,hi,inc,2*ind,L,M);
upd(lo,hi,inc,2*ind+1,M+1,R); pull(ind);
}
T query(int lo, int hi, int ind=1, int L=0, int R=SZ-1) {
push(ind,L,R); if (lo > R || L > hi) return ID;
if (lo <= L && R <= hi) return seg[ind];
int M = (L+R)/2; return cmb(query(lo,hi,2*ind,L,M),
query(lo,hi,2*ind+1,M+1,R));
}
};
template<int SZ, bool VALS_IN_EDGES> struct HLD {
int N; vector<int> adj[SZ];
int par[SZ], root[SZ], depth[SZ], sz[SZ], ti;
int pos[SZ]; vector<int> rpos; // rpos not used but could be useful
void ae(int x, int y) { adj[x].pb(y), adj[y].pb(x); }
void dfsSz(int x) {
sz[x] = 1;
for (auto& y : adj[x]) {
par[y] = x; depth[y] = depth[x]+1;
adj[y].erase(find(all(adj[y]),x)); /// remove parent from adj list
dfsSz(y); sz[x] += sz[y];
if (sz[y] > sz[adj[x][0]]) swap(y,adj[x][0]);
}
}
void dfsHld(int x) {
pos[x] = ti++; rpos.pb(x);
for (auto& y : adj[x]) {
root[y] = (y == adj[x][0] ? root[x] : y);
dfsHld(y); }
}
void init(int _N, int R = 0) { N = _N;
par[R] = depth[R] = ti = 0; dfsSz(R);
root[R] = R; dfsHld(R);
}
int lca(int x, int y) {
for (; root[x] != root[y]; y = par[root[y]])
if (depth[root[x]] > depth[root[y]]) swap(x,y);
return depth[x] < depth[y] ? x : y;
}
/// int dist(int x, int y) { // # edges on path
/// return depth[x]+depth[y]-2*depth[lca(x,y)]; }
LazySeg<Info,SZ,Lazy> tree; // segtree for sum
template <class BinaryOp>
void processPath(int x, int y, BinaryOp op) {
for (; root[x] != root[y]; y = par[root[y]]) {
if (depth[root[x]] > depth[root[y]]) swap(x,y);
op(pos[root[y]],pos[y]); }
if (depth[x] > depth[y]) swap(x,y);
op(pos[x]+VALS_IN_EDGES,pos[y]);
}
void modifyPath(int x, int y, const Lazy& v) {
processPath(x,y,[this,&v](int l, int r) {
tree.upd(l,r,v); }); }
Info queryPath(int x, int y) {
Info res = {}; processPath(x,y,[this,&res](int l, int r) {
res = res + tree.query(l,r); });
return res; }
};
HLD<1<<19, false> hld;
void solve() {
ll n, d;
cin >> n >> d;
vector e(n, vector<ll>());
for (int i = 0; i < n - 1; i++) {
ll x; cin >> x;
hld.ae(x, i + 1);
e[x].pb(i + 1);
e[i + 1].pb(x);
}
hld.init(n, 0);
vector<ll> depth(n);
auto dfs = [&](auto& dfs, ll g, ll p, ll d) -> void {
depth[g] = d;
hld.modifyPath(g, g, Lazy(INF, depth[g]));
for (auto u : e[g]) if (u != p) {
dfs(dfs, u, g, d + 1);
}
};
dfs(dfs, 0, -1, 0);
vector<ll> p(n);
iota(all(p), 0);
sort(all(p), [&](ll x, ll y) {
return depth[x] > depth[y];
});
vector<ll> ans;
for (auto u : p) {
Info to_root = hld.queryPath(0, u);
ll root_val = to_root.min_active - 2LL * to_root.max_depth;
if (root_val + depth[u] >= d) {
ans.pb(u);
// activate u
hld.modifyPath(0, u, Lazy(depth[u], -INF));
}
}
sort(all(ans));
cout << ans.size() << '\n';
for (const auto& u : ans)
cout << u + 1 << ' ';
cout << '\n';
}
int main() {
cin.tie(0)->sync_with_stdio(false);
solve();
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
23 ms |
45396 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
23 ms |
45396 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
23 ms |
45396 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
