kmjp's blog

競技プログラミング参加記です

AIM Tech Round 4 : C. Upgrading Tree

なんかパズル解いてるみたいだ。
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]);
}

まとめ

他の人のコード見ても理解するのにだいぶ手間取った。