九州大学プログラミングコンテスト2018 : G - Tapu & Tapi 2

うーむ、わかれば簡単なのだが。
https://beta.atcoder.jp/contests/qupc2018/tasks/qupc2018_g

問題

木を成す無向グラフが与えられる。各辺には重みがある。
一部の頂点にたぷ、また別の一部の頂点にたぴがいる。
両者が辺を辿って互いに行き来しないよういくつかの辺を減らしたい。
減らす辺の重みの総和の最小値を求めよ。

解法

この問題は、問題を言い換えると簡単になる。
これは行ってしまえば、頂点を２色に彩色する問題である。
ただし一部の頂点が色が指定されている。
異なる色の頂点を結ぶ辺の重みの総和を最小化するよう彩色したい。

そこで葉から順に各SubTreeにおいて、SubTreeの根頂点を白・黒それぞれに塗った場合のSubTreeの減らす辺の重みの総和を最小化するよう木DPしていこう。

int N,X,Y;
vector<pair<int,int>> E[505050];
ll dp[505050][2];

void dfs(int cur,int pre) {
	FORR(e,E[cur]) if(e.first!=pre) {
		dfs(e.first,cur);
		
		dp[cur][0]=min(1LL<<60,dp[cur][0]+min(dp[e.first][0],dp[e.first][1]+e.second));
		dp[cur][1]=min(1LL<<60,dp[cur][1]+min(dp[e.first][1],dp[e.first][0]+e.second));
	}
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>X>>Y;
	FOR(i,N-1) {
		cin>>x>>y>>r;
		E[x-1].push_back({y-1,r});
		E[y-1].push_back({x-1,r});
	}
	FOR(i,X) cin>>x, dp[x-1][1]=1LL<<60;
	FOR(i,Y) cin>>x, dp[x-1][0]=1LL<<60;
	dfs(0,-1);
	
	cout<<min(dp[0][0],dp[0][1])<<endl;
}

まとめ

この言い換えすんなり浮かばなかった。