30分代码求调
查看原帖
30分代码求调
1027690
IAKIOI__楼主2024/7/18 14:25
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int MAXN=2e3;
struct node{
	int from;
	int to;
}e[MAXN];
struct code{
	int dep;
	int id;
}d[MAXN];
int n,ans,head[MAXN],gp[MAXN],fa[MAXN],cnt;
priority_queue<pair<int,int> >q;
void add(int x,int y){
	e[++cnt].to=y;
	e[cnt].from=head[x];	
	head[x]=cnt;
}
void dfs(int x,int father,int de){
	d[x].dep=de;
	d[x].id=x;
	fa[x]=father;
	for(int i=head[x];i;i=e[i].from){
		if(e[i].to!=father)
		dfs(e[i].to,x,de+1);
	}
}
signed main(){
	cin>>n;
	for(int i=2,x;i<=n;i++){
		cin>>x;
		add(x,i);
		add(i,x);
	}
	dfs(1,1,1);
	for(int i=1;i<=n;i++){
		gp[i]=fa[fa[i]];
		q.push(make_pair(d[i].dep,d[i].id));
	}
	bool vis[MAXN];
	while(q.size()){
		ans++;
		int i=q.top().second;
		q.pop();vis[fa[i]]=vis[gp[i]]=1;
		for(int a=head[gp[i]];a;a=e[a].from){
			vis[e[a].to]=1;
			for(int b=head[e[a].to];b;b=e[b].from){
				vis[e[b].to]=1;
			}
		}
		for(int a=head[fa[i]];a;a=e[a].from){
			vis[e[a].to]=1;
		}
		while(q.size()&&vis[q.top().second]){q.pop();}
	}
	cout<<ans;
	return 0;
}
2024/7/18 14:25
加载中...