#include <bits/stdc++.h>
#define all(x) x.begin(), x.end()
#define sz(x) (int) x.size()
#define endl '\n'
#define pb push_back
#define _ ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
using namespace std;
using ll = long long;
using ull = unsigned long long;
using ii = pair<int,int>;
using iii = tuple<int,int,int>;
const int inf = 2e9+1;
const int mod = 1e9+7;
const int maxn = 2e5+100;
template<typename X, typename Y> bool ckmin(X& x, const Y& y) { return (y < x) ? (x=y,1):0; }
template<typename X, typename Y> bool ckmax(X& x, const Y& y) { return (x < y) ? (x=y,1):0; }
vector<int>g[maxn];
vector<ii>order;
int lift[maxn][20], sub[maxn], lvl[maxn], par[maxn], best[maxn];
bool vis[maxn];
void getOrder(int u,int p,int lvl){
order.pb({lvl,u});
for(auto v:g[u]){
if(v!=p)getOrder(v,u,lvl+1);
}
}
int dfs(int u,int p,int lvl){
if(lvl!=-1)lift[u][lvl] = lift[p][lvl]+1;
sub[u] = 1;
for(auto v:g[u]){
if(v==p||vis[v])continue;
sub[u] += dfs(v,u,lvl);
}
return sub[u];
}
int find_centroid(int u,int p,int n){
for(auto v:g[u]){
if(!vis[v]&&sub[v]>n/2&&v!=p)return find_centroid(v,u,n);
}
return u;
}
void build(int u=1,int p=-1){
int centroid = find_centroid(u,p,dfs(u,u,p==-1?p:lvl[p]));
vis[centroid] = 1, par[centroid] = p;
if(p!=-1)lvl[centroid] = lvl[p]+1;
for(auto v:g[centroid]){
if(!vis[v])build(v,centroid);
}
}
int lca(int u,int v){
if(lvl[u]<lvl[v])swap(u,v);
while(lvl[u]!=lvl[v])u=par[u];
while(u!=v)u=par[u],v=par[v];
return u;
}
int dist(int u,int v){
int level = lvl[lca(u,v)];
return lift[u][level] + lift[v][level];
}
void update(int u){
int source = u;
while(u!=-1){
if(best[u]==0||dist(source,u)<dist(best[u],u))best[u] = source;
u = par[u];
}
}
int query(int u){
int source = u, answer = inf;
while(u!=-1){
if(best[u]!=0)ckmin(answer,dist(source,best[u]));
u = par[u];
}
return answer;
}
int main(){_
int n,d;cin>>n>>d;
for(int i=2;i<=n;++i){
int x;cin>>x;++x;
g[x].pb(i);
g[i].pb(x);
}
getOrder(1,1,0);
sort(all(order));reverse(all(order));//order of node insertion
build();
int ans = 0;
for(int i=0;i<n;++i){
int cur = order[i].second;
if(query(cur)>=d){
update(cur), ++ans;
// cout<<cur<<" ";
}
}
cout<<ans<<endl;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
4 ms |
5012 KB |
Output is correct |
2 |
Correct |
3 ms |
5020 KB |
Output is correct |
3 |
Correct |
3 ms |
4948 KB |
Output is correct |
4 |
Correct |
3 ms |
5024 KB |
Output is correct |
5 |
Correct |
3 ms |
5020 KB |
Output is correct |
6 |
Correct |
3 ms |
5020 KB |
Output is correct |
7 |
Correct |
3 ms |
5028 KB |
Output is correct |
8 |
Correct |
3 ms |
5024 KB |
Output is correct |
9 |
Correct |
3 ms |
4948 KB |
Output is correct |
10 |
Correct |
3 ms |
4948 KB |
Output is correct |
11 |
Correct |
3 ms |
4948 KB |
Output is correct |
12 |
Correct |
3 ms |
4968 KB |
Output is correct |
13 |
Correct |
3 ms |
4948 KB |
Output is correct |
14 |
Correct |
3 ms |
5024 KB |
Output is correct |
15 |
Correct |
3 ms |
5028 KB |
Output is correct |
16 |
Correct |
3 ms |
5024 KB |
Output is correct |
17 |
Correct |
3 ms |
4948 KB |
Output is correct |
18 |
Correct |
3 ms |
5028 KB |
Output is correct |
19 |
Correct |
3 ms |
5020 KB |
Output is correct |
20 |
Correct |
3 ms |
5024 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
4 ms |
5012 KB |
Output is correct |
2 |
Correct |
3 ms |
5020 KB |
Output is correct |
3 |
Correct |
3 ms |
4948 KB |
Output is correct |
4 |
Correct |
3 ms |
5024 KB |
Output is correct |
5 |
Correct |
3 ms |
5020 KB |
Output is correct |
6 |
Correct |
3 ms |
5020 KB |
Output is correct |
7 |
Correct |
3 ms |
5028 KB |
Output is correct |
8 |
Correct |
3 ms |
5024 KB |
Output is correct |
9 |
Correct |
3 ms |
4948 KB |
Output is correct |
10 |
Correct |
3 ms |
4948 KB |
Output is correct |
11 |
Correct |
3 ms |
4948 KB |
Output is correct |
12 |
Correct |
3 ms |
4968 KB |
Output is correct |
13 |
Correct |
3 ms |
4948 KB |
Output is correct |
14 |
Correct |
3 ms |
5024 KB |
Output is correct |
15 |
Correct |
3 ms |
5028 KB |
Output is correct |
16 |
Correct |
3 ms |
5024 KB |
Output is correct |
17 |
Correct |
3 ms |
4948 KB |
Output is correct |
18 |
Correct |
3 ms |
5028 KB |
Output is correct |
19 |
Correct |
3 ms |
5020 KB |
Output is correct |
20 |
Correct |
3 ms |
5024 KB |
Output is correct |
21 |
Correct |
3 ms |
5332 KB |
Output is correct |
22 |
Correct |
3 ms |
5076 KB |
Output is correct |
23 |
Correct |
3 ms |
5076 KB |
Output is correct |
24 |
Correct |
3 ms |
5028 KB |
Output is correct |
25 |
Correct |
3 ms |
5148 KB |
Output is correct |
26 |
Correct |
3 ms |
5076 KB |
Output is correct |
27 |
Correct |
4 ms |
5076 KB |
Output is correct |
28 |
Correct |
4 ms |
5204 KB |
Output is correct |
29 |
Correct |
4 ms |
5204 KB |
Output is correct |
30 |
Correct |
4 ms |
5152 KB |
Output is correct |
31 |
Correct |
4 ms |
5204 KB |
Output is correct |
32 |
Correct |
4 ms |
5280 KB |
Output is correct |
33 |
Correct |
3 ms |
5216 KB |
Output is correct |
34 |
Correct |
3 ms |
5204 KB |
Output is correct |
35 |
Correct |
3 ms |
5152 KB |
Output is correct |
36 |
Correct |
3 ms |
5284 KB |
Output is correct |
37 |
Correct |
3 ms |
5292 KB |
Output is correct |
38 |
Correct |
3 ms |
5204 KB |
Output is correct |
39 |
Correct |
3 ms |
5204 KB |
Output is correct |
40 |
Correct |
4 ms |
5332 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
4 ms |
5012 KB |
Output is correct |
2 |
Correct |
3 ms |
5020 KB |
Output is correct |
3 |
Correct |
3 ms |
4948 KB |
Output is correct |
4 |
Correct |
3 ms |
5024 KB |
Output is correct |
5 |
Correct |
3 ms |
5020 KB |
Output is correct |
6 |
Correct |
3 ms |
5020 KB |
Output is correct |
7 |
Correct |
3 ms |
5028 KB |
Output is correct |
8 |
Correct |
3 ms |
5024 KB |
Output is correct |
9 |
Correct |
3 ms |
4948 KB |
Output is correct |
10 |
Correct |
3 ms |
4948 KB |
Output is correct |
11 |
Correct |
3 ms |
4948 KB |
Output is correct |
12 |
Correct |
3 ms |
4968 KB |
Output is correct |
13 |
Correct |
3 ms |
4948 KB |
Output is correct |
14 |
Correct |
3 ms |
5024 KB |
Output is correct |
15 |
Correct |
3 ms |
5028 KB |
Output is correct |
16 |
Correct |
3 ms |
5024 KB |
Output is correct |
17 |
Correct |
3 ms |
4948 KB |
Output is correct |
18 |
Correct |
3 ms |
5028 KB |
Output is correct |
19 |
Correct |
3 ms |
5020 KB |
Output is correct |
20 |
Correct |
3 ms |
5024 KB |
Output is correct |
21 |
Correct |
3 ms |
5332 KB |
Output is correct |
22 |
Correct |
3 ms |
5076 KB |
Output is correct |
23 |
Correct |
3 ms |
5076 KB |
Output is correct |
24 |
Correct |
3 ms |
5028 KB |
Output is correct |
25 |
Correct |
3 ms |
5148 KB |
Output is correct |
26 |
Correct |
3 ms |
5076 KB |
Output is correct |
27 |
Correct |
4 ms |
5076 KB |
Output is correct |
28 |
Correct |
4 ms |
5204 KB |
Output is correct |
29 |
Correct |
4 ms |
5204 KB |
Output is correct |
30 |
Correct |
4 ms |
5152 KB |
Output is correct |
31 |
Correct |
4 ms |
5204 KB |
Output is correct |
32 |
Correct |
4 ms |
5280 KB |
Output is correct |
33 |
Correct |
3 ms |
5216 KB |
Output is correct |
34 |
Correct |
3 ms |
5204 KB |
Output is correct |
35 |
Correct |
3 ms |
5152 KB |
Output is correct |
36 |
Correct |
3 ms |
5284 KB |
Output is correct |
37 |
Correct |
3 ms |
5292 KB |
Output is correct |
38 |
Correct |
3 ms |
5204 KB |
Output is correct |
39 |
Correct |
3 ms |
5204 KB |
Output is correct |
40 |
Correct |
4 ms |
5332 KB |
Output is correct |
41 |
Correct |
93 ms |
31984 KB |
Output is correct |
42 |
Correct |
141 ms |
19132 KB |
Output is correct |
43 |
Correct |
105 ms |
19120 KB |
Output is correct |
44 |
Correct |
93 ms |
18876 KB |
Output is correct |
45 |
Correct |
86 ms |
18844 KB |
Output is correct |
46 |
Correct |
311 ms |
33264 KB |
Output is correct |
47 |
Correct |
249 ms |
32824 KB |
Output is correct |
48 |
Correct |
272 ms |
32604 KB |
Output is correct |
49 |
Correct |
239 ms |
32572 KB |
Output is correct |
50 |
Correct |
61 ms |
19048 KB |
Output is correct |
51 |
Correct |
61 ms |
19024 KB |
Output is correct |
52 |
Correct |
60 ms |
19216 KB |
Output is correct |
53 |
Correct |
156 ms |
33020 KB |
Output is correct |
54 |
Correct |
156 ms |
33024 KB |
Output is correct |
55 |
Correct |
142 ms |
33004 KB |
Output is correct |
56 |
Correct |
4 ms |
5460 KB |
Output is correct |
57 |
Correct |
17 ms |
9684 KB |
Output is correct |
58 |
Correct |
77 ms |
25908 KB |
Output is correct |
59 |
Correct |
225 ms |
40480 KB |
Output is correct |
60 |
Correct |
90 ms |
32572 KB |
Output is correct |
61 |
Correct |
130 ms |
31792 KB |
Output is correct |