// Make the best become better
// No room for laziness
#include<bits/stdc++.h>
#define int long long
#define pb push_back
#define fi first
#define se second
using namespace std;
using ll = long long;
using ld = long double;
using ull = unsigned long long;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const int maxN = 1e6 + 5;
const int mod = 1e9 + 7;
const ll oo = 1e18;
int n, d;
vector<int> adj[maxN];
int depth[maxN];
int id[maxN];
int sz[maxN], vis[maxN];
int parCent[maxN];
int f[maxN][20];
void ReadInput()
{
cin >> n >> d;
for(int i=2; i<=n; i++)
{
int p;
cin >> p;
p++;
adj[p].pb(i);
adj[i].pb(p);
}
}
void predfs(int u, int par)
{
for(int v : adj[u])
{
if(v == par) continue;
depth[v] = depth[u] + 1;
f[v][0] = u;
for(int i=1; i<=18; i++)
f[v][i] = f[f[v][i - 1]][i - 1];
predfs(v, u);
}
}
int dfs(int u, int par)
{
sz[u] = 1;
for(int v : adj[u])
{
if(vis[v] || v == par) continue;
sz[u] += dfs(v, u);
}
return sz[u];
}
int Find_Centroid(int u, int par, int _sz)
{
for(int v : adj[u])
{
if(v == par || vis[v]) continue;
if(sz[v] > _sz / 2) return Find_Centroid(v, u, _sz);
}
return u;
}
int Decompose(int u)
{
int root = Find_Centroid(u, 0, dfs(u, 0));
vis[root] = -1;
for(int v : adj[root])
{
if(vis[v]) continue;
parCent[Decompose(v)] = root;
}
return root;
}
int lca(int u, int v)
{
if(depth[u] < depth[v]) swap(u, v);
int k = depth[u] - depth[v];
for(int i=18; i>=0; i--)
if((k >> i) & 1)
u = f[u][i];
if(u == v) return u;
for(int i=18; i>=0; i--)
if(f[u][i] != f[v][i])
{
u = f[u][i];
v = f[v][i];
}
return f[u][0];
}
int dist(int u, int v)
{
return depth[u] + depth[v] - 2 * depth[lca(u, v)];
}
int dp[maxN];
void upd(int u)
{
for(int v=u; v; v=parCent[v])
dp[v] = min(dp[v], dist(u, v));
}
int get(int u)
{
int res = oo;
for(int v=u; v; v=parCent[v])
res = min(res, dist(u, v) + dp[v]);
return res;
}
void Solve()
{
memset(dp, 3, sizeof dp);
predfs(1, 0);
iota(id + 1, id + n + 1, 1);
sort(id + 1, id + n + 1, [](int i, int j)
{
return depth[i] > depth[j];
});
int res = 0;
Decompose(1);
for(int i=1; i<=n; i++)
{
int j = id[i];
if(get(j) >= d)
{
res++;
upd(j);
}
}
cout << res;
}
int32_t main()
{
//freopen("sol.inp", "r", stdin);
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
ReadInput();
Solve();
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
16 ms |
31572 KB |
Output is correct |
2 |
Correct |
16 ms |
31688 KB |
Output is correct |
3 |
Correct |
15 ms |
31620 KB |
Output is correct |
4 |
Correct |
16 ms |
31620 KB |
Output is correct |
5 |
Correct |
15 ms |
31644 KB |
Output is correct |
6 |
Correct |
15 ms |
31624 KB |
Output is correct |
7 |
Correct |
14 ms |
31688 KB |
Output is correct |
8 |
Correct |
18 ms |
31572 KB |
Output is correct |
9 |
Correct |
19 ms |
31648 KB |
Output is correct |
10 |
Correct |
18 ms |
31572 KB |
Output is correct |
11 |
Correct |
18 ms |
31600 KB |
Output is correct |
12 |
Correct |
14 ms |
31656 KB |
Output is correct |
13 |
Correct |
19 ms |
31624 KB |
Output is correct |
14 |
Correct |
15 ms |
31572 KB |
Output is correct |
15 |
Correct |
15 ms |
31676 KB |
Output is correct |
16 |
Correct |
15 ms |
31568 KB |
Output is correct |
17 |
Correct |
14 ms |
31628 KB |
Output is correct |
18 |
Correct |
18 ms |
31572 KB |
Output is correct |
19 |
Correct |
17 ms |
31688 KB |
Output is correct |
20 |
Correct |
16 ms |
31572 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
16 ms |
31572 KB |
Output is correct |
2 |
Correct |
16 ms |
31688 KB |
Output is correct |
3 |
Correct |
15 ms |
31620 KB |
Output is correct |
4 |
Correct |
16 ms |
31620 KB |
Output is correct |
5 |
Correct |
15 ms |
31644 KB |
Output is correct |
6 |
Correct |
15 ms |
31624 KB |
Output is correct |
7 |
Correct |
14 ms |
31688 KB |
Output is correct |
8 |
Correct |
18 ms |
31572 KB |
Output is correct |
9 |
Correct |
19 ms |
31648 KB |
Output is correct |
10 |
Correct |
18 ms |
31572 KB |
Output is correct |
11 |
Correct |
18 ms |
31600 KB |
Output is correct |
12 |
Correct |
14 ms |
31656 KB |
Output is correct |
13 |
Correct |
19 ms |
31624 KB |
Output is correct |
14 |
Correct |
15 ms |
31572 KB |
Output is correct |
15 |
Correct |
15 ms |
31676 KB |
Output is correct |
16 |
Correct |
15 ms |
31568 KB |
Output is correct |
17 |
Correct |
14 ms |
31628 KB |
Output is correct |
18 |
Correct |
18 ms |
31572 KB |
Output is correct |
19 |
Correct |
17 ms |
31688 KB |
Output is correct |
20 |
Correct |
16 ms |
31572 KB |
Output is correct |
21 |
Correct |
16 ms |
32084 KB |
Output is correct |
22 |
Correct |
15 ms |
31760 KB |
Output is correct |
23 |
Correct |
15 ms |
31712 KB |
Output is correct |
24 |
Correct |
15 ms |
31756 KB |
Output is correct |
25 |
Correct |
15 ms |
31876 KB |
Output is correct |
26 |
Correct |
17 ms |
31828 KB |
Output is correct |
27 |
Correct |
18 ms |
31860 KB |
Output is correct |
28 |
Correct |
22 ms |
31956 KB |
Output is correct |
29 |
Correct |
17 ms |
31976 KB |
Output is correct |
30 |
Correct |
19 ms |
31924 KB |
Output is correct |
31 |
Correct |
16 ms |
31956 KB |
Output is correct |
32 |
Correct |
17 ms |
31956 KB |
Output is correct |
33 |
Correct |
17 ms |
31928 KB |
Output is correct |
34 |
Correct |
19 ms |
31956 KB |
Output is correct |
35 |
Correct |
20 ms |
32008 KB |
Output is correct |
36 |
Correct |
22 ms |
31956 KB |
Output is correct |
37 |
Correct |
18 ms |
31956 KB |
Output is correct |
38 |
Correct |
17 ms |
32044 KB |
Output is correct |
39 |
Correct |
17 ms |
32016 KB |
Output is correct |
40 |
Correct |
16 ms |
32008 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
16 ms |
31572 KB |
Output is correct |
2 |
Correct |
16 ms |
31688 KB |
Output is correct |
3 |
Correct |
15 ms |
31620 KB |
Output is correct |
4 |
Correct |
16 ms |
31620 KB |
Output is correct |
5 |
Correct |
15 ms |
31644 KB |
Output is correct |
6 |
Correct |
15 ms |
31624 KB |
Output is correct |
7 |
Correct |
14 ms |
31688 KB |
Output is correct |
8 |
Correct |
18 ms |
31572 KB |
Output is correct |
9 |
Correct |
19 ms |
31648 KB |
Output is correct |
10 |
Correct |
18 ms |
31572 KB |
Output is correct |
11 |
Correct |
18 ms |
31600 KB |
Output is correct |
12 |
Correct |
14 ms |
31656 KB |
Output is correct |
13 |
Correct |
19 ms |
31624 KB |
Output is correct |
14 |
Correct |
15 ms |
31572 KB |
Output is correct |
15 |
Correct |
15 ms |
31676 KB |
Output is correct |
16 |
Correct |
15 ms |
31568 KB |
Output is correct |
17 |
Correct |
14 ms |
31628 KB |
Output is correct |
18 |
Correct |
18 ms |
31572 KB |
Output is correct |
19 |
Correct |
17 ms |
31688 KB |
Output is correct |
20 |
Correct |
16 ms |
31572 KB |
Output is correct |
21 |
Correct |
16 ms |
32084 KB |
Output is correct |
22 |
Correct |
15 ms |
31760 KB |
Output is correct |
23 |
Correct |
15 ms |
31712 KB |
Output is correct |
24 |
Correct |
15 ms |
31756 KB |
Output is correct |
25 |
Correct |
15 ms |
31876 KB |
Output is correct |
26 |
Correct |
17 ms |
31828 KB |
Output is correct |
27 |
Correct |
18 ms |
31860 KB |
Output is correct |
28 |
Correct |
22 ms |
31956 KB |
Output is correct |
29 |
Correct |
17 ms |
31976 KB |
Output is correct |
30 |
Correct |
19 ms |
31924 KB |
Output is correct |
31 |
Correct |
16 ms |
31956 KB |
Output is correct |
32 |
Correct |
17 ms |
31956 KB |
Output is correct |
33 |
Correct |
17 ms |
31928 KB |
Output is correct |
34 |
Correct |
19 ms |
31956 KB |
Output is correct |
35 |
Correct |
20 ms |
32008 KB |
Output is correct |
36 |
Correct |
22 ms |
31956 KB |
Output is correct |
37 |
Correct |
18 ms |
31956 KB |
Output is correct |
38 |
Correct |
17 ms |
32044 KB |
Output is correct |
39 |
Correct |
17 ms |
32016 KB |
Output is correct |
40 |
Correct |
16 ms |
32008 KB |
Output is correct |
41 |
Correct |
165 ms |
76484 KB |
Output is correct |
42 |
Correct |
224 ms |
55520 KB |
Output is correct |
43 |
Correct |
191 ms |
55500 KB |
Output is correct |
44 |
Correct |
172 ms |
55488 KB |
Output is correct |
45 |
Correct |
174 ms |
55628 KB |
Output is correct |
46 |
Correct |
445 ms |
79448 KB |
Output is correct |
47 |
Correct |
407 ms |
79436 KB |
Output is correct |
48 |
Correct |
400 ms |
79452 KB |
Output is correct |
49 |
Correct |
405 ms |
79572 KB |
Output is correct |
50 |
Correct |
116 ms |
55712 KB |
Output is correct |
51 |
Correct |
131 ms |
55756 KB |
Output is correct |
52 |
Correct |
113 ms |
55800 KB |
Output is correct |
53 |
Correct |
269 ms |
80004 KB |
Output is correct |
54 |
Correct |
249 ms |
79900 KB |
Output is correct |
55 |
Correct |
251 ms |
80008 KB |
Output is correct |
56 |
Correct |
19 ms |
32212 KB |
Output is correct |
57 |
Correct |
42 ms |
37844 KB |
Output is correct |
58 |
Correct |
173 ms |
60808 KB |
Output is correct |
59 |
Correct |
492 ms |
85660 KB |
Output is correct |
60 |
Correct |
148 ms |
77636 KB |
Output is correct |
61 |
Correct |
272 ms |
76664 KB |
Output is correct |