DP 30pts求调
查看原帖
DP 30pts求调
373530
Reply_楼主2025/7/24 13:42
#include<bits/stdc++.h>
#define ll long long
#define R1 register
#define F(i,a,b) for(int i = (a);i<=(b);i++)
using namespace std;
inline int read(){R1 int x=0,t=1;R1 char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-') t=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}return x*t;}
const int N=2e5+10;
vector<int>g[N];
void add(int ui,int vi)
{
	g[ui].push_back(vi);
	return;
}
int f[N][5];
void dfs(int u,int fa)
{
	if(g[u].size()==1 && g[u][0]==fa){//叶子
		f[u][0]=f[u][1]=f[u][2]=1;
		f[u][3]=f[u][4]=0;
		return;
	}
	f[u][0]=1;
	for(int v:g[u]){
		if(v==fa) continue;
		dfs(v,u);
		f[u][0]+=f[v][4];
		f[u][1]+=f[v][3];
		f[u][2]+=f[v][2];
		f[u][3]+=f[v][2];
		f[u][4]+=f[v][3];
	}
	int min1=1e9,min2=1e9;
	for(int v:g[u]){
		min1=min(min1,f[v][0]-f[v][3]);
		min2=min(min2,f[v][1]-f[v][2]);
	}
	f[u][1]+=min1;
	f[u][2]+=min2;
	for(int i = 1;i<5;i++) f[u][i]=min(f[u][i],f[u][i-1]);
//	printf("%d %d %d %d %d %d\n",u,f[u][0],f[u][1],f[u][2],f[u][3],f[u][4]);
	return;
}
signed main()
{
	int n=read();
	for(int i = 2;i<=n;i++){
		int u=read();
		add(u,i);
		add(i,u);
	}
	dfs(1,0);
	cout << f[1][2] << '\n';
	return 0;
}
2025/7/24 13:42
加载中...