手こずったけど、問題設定自体は嫌いじゃない。
https://csacademy.com/contest/round-60/task/flip-the-edges/
問題
木を成すグラフが与えられる。
各辺は赤青いずれかの色が与えられる。
この木に対し、いくつかのパスを設定したい。
個々のパスは同じ頂点・辺を複数回含めることはできないが、異なるパスで重複しても構わない。
なお、各辺パスが1本通る毎に赤青反転する。
各辺、ターゲットとなる色が与えられる。また辺によっては色はどちらでも構わないとする。
そのような色を実現できるパスの最小本数と総長を求めよ。
最小本数が同じパスの組み合わせが多数あるなら、パスの総長の最小値を求めよ。
解法
最初とターゲットの色の指定から、各辺は以下のいずれかであることがわかる。
- 最初とターゲットの色が同じ場合:パスが偶数本通る
- 最初とターゲットの色が異なる場合:パスが奇数本通る
- ターゲットの色が構わない場合:パスの本数は問わない
なお、同じパス数でも総長を短くするという指定より、実際には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; }
まとめ
考え方はさほど難しくないはずだが、妙に手間取った。