!一蒟蒻P2458树形DP代码被外星人加入草履虫导致WA90分,求调
  • 板块灌水区
  • 楼主Zq_water
  • 当前回复1
  • 已保存回复1
  • 发布时间2024/8/2 20:24
  • 上次更新2024/8/2 21:15:26
查看原帖
!一蒟蒻P2458树形DP代码被外星人加入草履虫导致WA90分,求调
895435
Zq_water楼主2024/8/2 20:24

rt

#include<bits/stdc++.h>
#define INF 2e18
#define endl '\n'
#define PI acos(-1)
#define pb push_back
#define fi first
#define se second
#define int long long
#define mem(x,v) memset(x,v,sizeof x)
using namespace std;
const int N = 1.5e3+5;

int n,a[N],f[N][3];
vector <int> g[N];

void dfs(int u,int fa){
	int t=INF;
	for(int v:g[u]){
		if(v==fa)continue;
		dfs(v,u);
		f[u][0]+=min(f[v][0],f[v][2]);
		t=min(t,f[v][2]-min(f[v][0],f[v][2]));
		f[u][1]+=min(f[v][0],f[v][2]);
		f[u][2]+=min({f[v][0],f[v][1],f[v][2]});
	}
	f[u][0]+=t,f[u][2]+=a[u];
}
signed main(){
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	cin>>n;
	for(int i=1,id,k,num,x;i<=n;i++){
		cin>>id>>k>>num,a[id]=k;
		while(num--)cin>>x,g[id].pb(x);
	}
	dfs(1,0),cout<<min(f[1][0],f[1][2]);
	return 0;
}
2024/8/2 20:24
加载中...