答案错误求调(玄关)
查看原帖
答案错误求调(玄关)
970208
bfs_MST楼主2024/8/25 11:34

rt各位大佬,树形dp答案错误应该怎么改

#include <bits/stdc++.h>
#define N 200005
using namespace std;

bool vis[N],a[N];
int n,m,dp[N],st;
vector <int> e[N];

void in1()
{
	int x,y;
	scanf("%d%d", &x, &y);
	e[x].emplace_back(y);
	e[y].emplace_back(x);
}

void in2()
{
	
	int x;
	scanf("%d", &x);
	if(st == 0) st = x;
	a[x] = true;
}

void dfs(int x,int f)
{
	for(auto v : e[x])
	{
		if(v == f) continue;
		dfs(v,x);
		vis[x] = vis[v];
		dp[x] += dp[v];
	}
	if(a[x]) vis[x] = true;
	if(!vis[x]) dp[x]++;
}

int main()
{
	cin >> n >> m;
	for(int i = 1; i < n; i++) in1();
	for(int i = 1; i <= m; i++) in2();
	dfs(st,0);
	cout << n - dp[st];
}
2024/8/25 11:34
加载中...