yukicoder : No.912 赤黒木

シンプルな設定でいいね。
https://yukicoder.me/problems/no/912

問題

N頂点の無向グラフで、赤辺と黒辺が(N-1)本ずつあり、それぞれ木を成している。
黒辺を各1回ずつ通り、赤辺を任意回数通るようなパスのうち最短の長さを求めよ。

解法

一筆書きの条件を考えると、黒辺で構成された木において、次数が奇数の頂点のうち、2個を除いたものの間は赤辺でパスをつながないといけないことになる。
よって、赤辺で構成される木において、以下を「赤辺でつながれていない奇数次数頂点」を貪欲にペアにしつつ、DPで求めていけばよい。
f(v,num,b) := 頂点vのSubtreeのうち、除いた黒辺奇数次数頂点がnum個で、それ以外でまだ赤辺でつながれていない奇数次数頂点の有無がbで現れる場合の、赤辺の総長(b=Trueの場合、加えてその頂点の深さ)の最小値

int N;
vector<int> R[201010],B[201010];
ll dp[202020][3][2];

void dfs(int cur,int pre,int d) {
	if(B[cur].size()%2) {
		dp[cur][0][0]=1LL<<40;
		dp[cur][0][1]=d;
		dp[cur][1][0]=0;
		dp[cur][1][1]=1LL<<40;;
		dp[cur][2][0]=dp[cur][2][1]=1LL<<40;
	}
	else {
		dp[cur][0][0]=0;
		dp[cur][0][1]=1LL<<40;
		dp[cur][1][0]=1LL<<40;
		dp[cur][1][1]=1LL<<40;;
		dp[cur][2][0]=dp[cur][2][1]=1LL<<40;
	}
	FORR(e,R[cur]) if(e!=pre) {
		dfs(e,cur,d+1);
		ll p[3][2];
		int a,b;
		FOR(a,3) FOR(b,2) p[a][b]=dp[cur][a][b];
		FOR(a,3) FOR(b,2) dp[cur][a][b]=1LL<<40;
		FOR(a,3) for(b=0;a+b<=2;b++) {
			dp[cur][a+b][0]=min({dp[cur][a+b][0],p[a][0]+dp[e][b][0],p[a][1]+dp[e][b][1]-2*d});
			dp[cur][a+b][1]=min({dp[cur][a+b][1],p[a][0]+dp[e][b][1],p[a][1]+dp[e][b][0]});
		}
	}
	
}


void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N-1) {
		cin>>x>>y;
		R[x-1].push_back(y-1);
		R[y-1].push_back(x-1);
	}
	FOR(i,N-1) {
		cin>>x>>y;
		B[x-1].push_back(y-1);
		B[y-1].push_back(x-1);
	}
	dfs(0,-1,0);
	cout<<(N-1)+min(dp[0][0][0],dp[0][2][0])<<endl;
}

まとめ

最初2個無視できることを忘れて書いてしまった。