#C221110A. PolarSea与边割集

标签（Label）

动态规划

网址（Website）

题目详情 - PolarSea与边割集 - Super

题解 - PolarSea与边割集 - Super

题解（Solution）

出题者题解

算法分析

考虑从底向上树形 $dp$。

$f_{i,0}$ 表示做完 $i$ 的子树后，$i$ 既不与 $a$ 中的点相连，也不与 $b$ 中的点相连的最小花费。

$f_{i,1}$ 表示做完 $i$ 的子树后，$i$ 只与 $a$ 中的点相连的最小花费。

$f_{i,2}$ 表示做完 $i$ 的子树后，$i$ 只与 $b$ 中的点相连的最小花费。

转移时讨论一下是否删边即可。时间复杂度为 $O(n)$。

代码（Code）

#include<bits/stdc++.h>
#include<vector>
#include<queue>
#define For(i,l,r) for(int i=l;i<=r;i++)
#define Rof(i,l,r) for(int i=l;i>=r;i--)
using namespace std;
#define P pair<int,int> 
#define int long long
#define x first
#define y second
inline int rd(){
	char c;bool f=false;while(!isdigit(c=getchar()))f=c=='-';int x=c^48;
	while(isdigit(c=getchar())){x=(((x<<2)+x)<<1)+(c^48);}return f?-x:x;
}const int inf = 0x3f3f3f3f3f3f3f3f;
const int N = 501234;
bool ST;

int n,m,s,t,mx,ans,c[N];
vector<P> ft[N];
int f[N][3];

inline void dfs(int x,int fa){
	if(c[x]==1){
		f[x][0] = f[x][2] = inf;
		for(auto p:ft[x]){
			int y = p.x, v = p.y;
			if(y==fa) continue;
			dfs(y,x);
			f[x][1] += min({f[y][0], f[y][1], f[y][2]+v});
		}
	}else if(c[x]==2){
		f[x][0] = f[x][1] = inf;
		for(auto p:ft[x]){
			int y = p.x, v = p.y;
			if(y==fa) continue;
			dfs(y,x);
			f[x][2] += min({f[y][0], f[y][1]+v, f[y][2]});
		}
	}else{
		for(auto p:ft[x]){
			int y = p.x, v = p.y;
			if(y==fa) continue;
			dfs(y,x);
			f[x][0] += min({f[y][0], f[y][1]+v, f[y][2]+v});
			f[x][1] = min({f[x][1]+f[y][0], f[x][1]+f[y][1], f[x][1]+f[y][2]+v, f[x][0]+f[y][1]});
			f[x][2] = min({f[x][2]+f[y][0], f[x][2]+f[y][1]+v, f[x][2]+f[y][2], f[x][0]+f[y][2]});
		}
	}
}

inline void solve(){
	n = rd();
	For(i,1,n-1){
		int x = rd(), y = rd(), v = rd();
		ft[x].emplace_back(y,v);
		ft[y].emplace_back(x,v);
	}
	s = rd(); For(i,1,s) c[rd()] = 1;
	t = rd(); For(i,1,t) c[rd()] = 2;
	dfs(1,0);
	printf("%lld\n",min({f[1][0],f[1][1],f[1][2]}));
}

bool ED;
signed main(){
	cerr<<abs(&ST-&ED)/1024./1024.<<"MB\n";
	freopen("cut.in","r",stdin);
	freopen("cut.out","w",stdout);
	int T = 1, Tim = clock();
	while(T--) solve();
	return cerr<<"TIME:"<<(clock()-Tim)/1000.,0;
}