树形dp 84pts WA了第一个点 求调!!!
查看原帖
树形dp 84pts WA了第一个点 求调!!!
718685
lym2022楼主2024/8/5 09:12
#include<bits/stdc++.h>
using namespace std;
#define int long long

const int N = 1505;

int n,in[N],root,f[N][2];

bool vis[N];

vector<int> e[N];

void dfs(int u,int fa) {
	f[u][1] = 1;
	f[u][0] = 0;
	for(auto i : e[u]) {
		if(i == fa) continue;
		dfs(i,u);
		f[u][0] += f[i][1];
		f[u][1] += min(f[i][0],f[i][1]);
	}
}

signed main() {
	cin >> n;
	for(int i = 0;i<n;i++) {
		int x,k;
		cin >> x >> k;
		for(int j = 0;j<k;j++) {
			int r;
			cin >> r;
			e[x].push_back(r);
			e[r].push_back(x);
			in[r]++;
		}
	}
	for(int i = 0;i<n;i++) {
		if(!in[i]) {
			root = i;
			break;
		}
	}
	dfs(root,0);
	cout << min(f[0][0],f[0][1]);
	return 0;
}
2024/8/5 09:12
加载中...