CSAcademy Round #60 : E. Flip the Edges

手こずったけど、問題設定自体は嫌いじゃない。
https://csacademy.com/contest/round-60/task/flip-the-edges/

問題

木を成すグラフが与えられる。
各辺は赤青いずれかの色が与えられる。

この木に対し、いくつかのパスを設定したい。
個々のパスは同じ頂点・辺を複数回含めることはできないが、異なるパスで重複しても構わない。
なお、各辺パスが１本通る毎に赤青反転する。

各辺、ターゲットとなる色が与えられる。また辺によっては色はどちらでも構わないとする。
そのような色を実現できるパスの最小本数と総長を求めよ。
最小本数が同じパスの組み合わせが多数あるなら、パスの総長の最小値を求めよ。

解法

最初とターゲットの色の指定から、各辺は以下のいずれかであることがわかる。

• 最初とターゲットの色が同じ場合：パスが偶数本通る
• 最初とターゲットの色が異なる場合：パスが奇数本通る
• ターゲットの色が構わない場合：パスの本数は問わない

なお、同じパス数でも総長を短くするという指定より、実際には0本か1本しか通す必要はない。
よって、パスを偶数本通す辺は最初からなかったものとし、あとは個々の連結成分について考えよう。

あとは良くある木DPで、親方向の辺をパスが0本通る場合と1本通る場合それぞれについて、SubTree内のパス数と総長の最小値を更新していけばよい。

int N;
vector<pair<int,int>> E[101010];
int vis[101010];
ll P[101010][2];
ll L[101010][2];

void dfs(int cur,int pre) {
	int tar=-1;
	vis[cur]=1;
	P[cur][1]=L[cur][1]=1LL<<50;
	FORR(e,E[cur]) {
		int t=e.first;
		if(t==pre) {
			tar=e.second;
			continue;
		}
		pair<ll,ll> T[2];
		dfs(t,cur);
		
		T[0]=min(make_pair(P[cur][0]+P[t][0],L[cur][0]+L[t][0]),make_pair(P[cur][1]+P[t][1]-1,L[cur][1]+L[t][1]));
		T[1]=min(make_pair(P[cur][0]+P[t][1],L[cur][0]+L[t][1]),make_pair(P[cur][1]+P[t][0],L[cur][1]+L[t][0]));
		
		P[cur][0]=T[0].first;
		P[cur][1]=T[1].first;
		L[cur][0]=T[0].second;
		L[cur][1]=T[1].second;
		
	}
	
	if(tar==1) {
		pair<ll,ll> T=min(make_pair(P[cur][0]+1,L[cur][0]+1),make_pair(P[cur][1],L[cur][1]+1));
		P[cur][1]=T.first;
		L[cur][1]=T.second;
		P[cur][0]=L[cur][0]=1LL<<50;
	}
	else {
		pair<ll,ll> T[2];
		T[0]=min(make_pair(P[cur][0],L[cur][0]),make_pair(P[cur][1],L[cur][1]));
		T[1]=min(make_pair(P[cur][0]+1,L[cur][0]+1),make_pair(P[cur][1],L[cur][1]+1));
		
		P[cur][0]=T[0].first;
		P[cur][1]=T[1].first;
		L[cur][0]=T[0].second;
		L[cur][1]=T[1].second;
	}
	
	
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N-1) {
		cin>>x>>y>>j>>k;
		if(j==k) continue;
		x--;
		y--;
		E[x].push_back({y,k!=2});
		E[y].push_back({x,k!=2});
	}
	
	ll PR=0,LR=0;
	FOR(i,N) if(vis[i]==0) {
		dfs(i,-1);
		PR+=P[i][0];
		LR+=L[i][0];
	}
	cout<<PR<<" "<<LR<<endl;
	
}

まとめ

考え方はさほど難しくないはずだが、妙に手間取った。