求条90pts
查看原帖
求条90pts
1171250
w132326820楼主2024/12/14 17:48

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=200010,P=99999999;
int n,w[N],m;
int x,y;
vector<int>v[N];
int f[N][3];
void dfs(int x,int fa){
	f[x][1]=w[x];
	f[x][2]=P;
	for(int i=0;i<v[x].size();i++){
		int u=v[x][i];
		if(u!=fa){
			dfs(u,x);
			f[x][0]+=min(f[u][1],f[u][2]);
			f[x][1]+=min({f[u][1],f[u][2],f[u][0]});
		}
	}
	for(int i=0;i<v[x].size();i++){
		int u=v[x][i];
		if(u!=fa){
			f[x][2]=min(f[x][2],f[x][0]+f[u][1]-min(f[u][1],f[u][2]));
		}
	}
}
signed main(){
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>x>>w[i]>>m;
		for(int j=1;j<=m;j++){
			cin>>y;
			v[x].push_back(y);
			v[y].push_back(x);
		}
	}
	dfs(1,0);
	cout<<min(f[1][1],f[1][2]);
	return 0;
}

2024/12/14 17:48
加载中...