なんかパズル解いてるみたいだ。
http://codeforces.com/contest/843/problem/C
問題
木を成すN頂点のグラフが与えられる。
以下の処理を任意回数行うことを考える。
辺(x-y)を選び辺を取り除く。
こうして分かれたx側とy側の連結成分のうちy側の頂点が少ないとすると、y側の連結成分から1つ頂点y'を選び、x-y'を再度辺で結ぶ。
上記処理を2N回以下まで行い、頂点間の距離の二乗和を最小化せよ。
解法
問題の定義より、重心となる頂点vに関してはx側にしかなれずy側になることはできない。
よってもともと重心につながる(重心でない)頂点がa個あるとすると、何回変形してもa個にしかならない。
そこで、重心を根としたとき、重心の隣接点についてそのSubTree中の頂点がすべて隣接点に直結する(いわゆるウニ形状になる)ように結び変えよう。
重心をA,その隣接点をB(ウニの中心)とし、そこからDFSで頂点をつなぎかえる。
頂点Dを処理するときには親頂点Cはすでに処理済みなので隣接点につながるため、A~Dまでのパスはこのような並びになっているはずである。
A--B--C--D--E--***
以下の3手順を行おう。
- A-Bを切りA-Dをつなぐ。
- C-Dを切りB-Dをつなぐ
- A-Dを切りA-Bをつなぐ
こうすると以下のようにつなぎ替えができる。
A--B--C | D--E--***
ただ、この手順だと1頂点3回処理を行うので、全体の処理手順を2N回に押さえることができない。
Dに関する最後の処理でA-Dを切りA-Bをつないでいるが、次にDFSでEを処理するとき、そのA-Bはどうせ再度切ってしまう。
そのため、この両者を合わせて1回で行うようにすれば全体を2N回で押さえられる。
int N; vector<int> E[202020]; set<int> center; vector<vector<int>> ret; int last=-1; int dfs(int cur,int pre) { int C=1; int ok=1; FORR(e,E[cur]) if(e!=pre) { int x=dfs(e,cur); if(x>N/2) ok=0; C+=x; } if(N-C>N/2) ok=0; if(ok) center.insert(cur); return C; } void dfs2(int cur,int pre,int cent,int nex) { if(pre!=nex) { ret.push_back({cent,last,cur}); ret.push_back({cur,pre,nex}); last=cur; } FORR(e,E[cur]) if(e!=pre) dfs2(e,cur,cent,nex); } void solve() { int i,j,k,l,r,x,y; string s; cin>>N; FOR(i,N-1) { cin>>x>>y; E[x].push_back(y); E[y].push_back(x); } dfs(1,-1); FORR(c,center) { FORR(e,E[c]) if(center.count(e)==0) { last=e; FORR(e2,E[e]) if(e2!=c) dfs2(e2,e,c,e); if(last>=0) ret.push_back({c,last,e}); } } _P("%d\n",ret.size()); FORR(r,ret) _P("%d %d %d\n",r[0],r[1],r[2]); }
まとめ
他の人のコード見ても理解するのにだいぶ手間取った。