树形 DP 全 mle 球条
查看原帖
树形 DP 全 mle 球条
973540
Kun_is_Me楼主2025/7/23 17:07
#include<bits/stdc++.h>
using namespace std;
int n;
struct edge{int to,next;}e[1145]; 
int head[1145];
int f[1145][5];
int ne=0;
void adde(int u, int v)
{
	e[++ne].to=v;
	e[ne].next=head[u];
	head[u]=ne;
}
void dfs(int now)
{
    f[now][0]=1;
	f[now][3]=0;
	f[now][4]=0;
	for(int i=head[now];i;i=e[i].next)
    {
		int s=e[i].to;
		dfs(s);
		f[now][0]+=f[s][4],f[now][3]+=f[s][2],f[now][4]+=f[s][3];
	}
	if(head[now]==0) f[now][1]=f[now][2]=1;
	else
    {
        f[now][1]=f[now][2]=114514;
		for(int i=head[now];i;i=e[i].next)
        {
			int s=e[i].to,F1=f[s][0],F2=f[s][1];
			for(int j=head[now];j;j=e[j].next)
            {
				if(i==j) continue;
				int t=e[j].to;
				F1+=f[t][3];
				F2+=f[t][2];
			}
			f[now][1]=min(f[now][1],F1);
			f[now][2]=min(f[now][2],F2);
		}
	}
	for(int i=1;i<=4;i++) f[now][i]=min(f[now][i],f[now][i-1]);
}
int main()
{
	cin>>n;
	for(int i=1,x;i<n;i++) cin>>x,adde(x,i),adde(i,x);
	dfs(1);
	cout<<f[1][2];
    return 0;
}
2025/7/23 17:07
加载中...