本番方針はあっていたけど、しょうもないバッファオーバーフローで落ちた。
http://codeforces.com/contest/581/problem/F
問題
N頂点の木を成すグラフが与えられる。
この木の葉は偶数である。
各頂点を白黒2色で塗り分けることを考える。
その際、葉となる頂点は白黒同数となるようにしたい。
上記条件を満たす塗り分け方において、白頂点と黒頂点を結ぶ辺の数の最小数を求めよ。
解法
仮に初期状態で全頂点白とする。
葉でない頂点から初めてDFSを行い、「以下のsubtreeの頂点をすべて白黒反転する/しない」場合に、subtreeにおける白黒な葉頂点の差を計算していく。
そして白黒葉頂点数の差ごとに、必要な反転回数の最小値を求めるDPをしていけば良い。
一見O(N^3)でO(N^2)で終わるタイプの木DP。
int N,D; vector<int> E[5050]; int mi[5050]; int ma[5050]; int dp[5050][7100]; void dfs(int cur,int pre) { // last if(E[cur].size()==1) { dp[cur][3000+1]=0; mi[cur]=ma[cur]=1; } else { dp[cur][3000+0]=0; mi[cur]=ma[cur]=0; int x,y; FORR(tar,E[cur]) if(tar!=pre) { int tmp[7000]; FOR(x,7000) tmp[x]=10000000; dfs(tar,cur); for(x=mi[cur];x<=ma[cur];x++) if(dp[cur][3000+x]<1000000) { for(y=mi[tar];y<=ma[tar];y++) if(dp[tar][3000+y]<1000000) { if(x+y<=D/2 && x+y>=-D/2) tmp[3000+x+y]=min(tmp[3000+x+y],dp[cur][3000+x]+dp[tar][3000+y]); if(x-y<=D/2 && x-y>=-D/2) tmp[3000+x-y]=min(tmp[3000+x-y],dp[cur][3000+x]+dp[tar][3000+y]+1); } } mi[cur]=max(-D/2, min(mi[cur]+mi[tar],mi[cur]-ma[tar])); ma[cur]=min(D/2,max(ma[cur]-mi[tar],ma[cur]+ma[tar])); for(x=mi[cur];x<=ma[cur];x++) dp[cur][3000+x]=tmp[3000+x]; } } int x; } void solve() { int i,j,k,l,r,x,y; string s; memset(dp,0x7f,sizeof(dp)); cin>>N; FOR(i,N-1) { cin>>x>>y; E[x-1].push_back(y-1); E[y-1].push_back(x-1); } int st=N+1; FOR(i,N) { if(E[i].size()==1) D++; else st=min(st,i); } if(D==2) return _P("1\n"); dfs(st,-1); cout<<dp[st][3000]<<endl; }
まとめ
Eよりだいぶ楽。