kmjp's blog

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

Codeforces #328 Div2 D. Super M

問題文わかりにくすぎじゃないですかね…。
http://codeforces.com/contest/592/problem/D

問題

N頂点からなる木を成すグラフが与えられる。
各辺の長さは1である。

ここでM個の頂点が指定される。
任意の頂点から開始し、指定された頂点を最低1回ずつ通りたい。
移動距離を最小化するには、どの頂点から開始すればよいか。またその時の移動距離を求めよ。

解法

まず、指定された頂点の一つからDFSし、指定頂点がないsubtreeを切り落としておこう。
すると、単に残ったグラフの全頂点を通る最短経路を求める問題となる。

ある点から初めて全部たどる、だと難しいので、全部の辺を辿って元の位置に戻る閉路を考え、そこから最遠の2点間の移動を間引くことにする。
閉路長は残った辺の数の2倍なので、後は最遠の2点をDFS2回で求めていこう。
1回目で各点から葉までの最長距離を求め、2回目で親側の最長距離を求めればよい。

int N,M,P;
vector<int> E[200000];
int man[202020];
vector<pair<int,int> > V;

int cd;
int st;
vector<pair<int,int>> D[202020];
int ma=0,cand=0;

int dfs(int cur,int pre) {
	FORR(r,E[cur]) if(r!=pre) D[cur].push_back({dfs(r,cur),r});
	D[cur].push_back({0,cur});
	return max_element(ALL(D[cur]))->first+1;
}

void dfs2(int cur,int pre,int par) {
	if(pre>=0) D[cur].push_back({par,pre});
	sort(ALL(D[cur]));
	reverse(ALL(D[cur]));
	int i;
	
	if(D[cur][0].first>ma || (D[cur][0].first==ma && cur<cand)) ma=D[cur][0].first,cand=cur;
	
	FORR(r,E[cur]) if(r!=pre) dfs2(r,cur,D[cur][(D[cur][0].second==r)].first+1);
	
	return;
}

int prune(int cur,int pre) {
	int num=0;
	vector<int> nn;
	FORR(r,E[cur]) if(r!=pre) {
		int n=prune(r,cur);
		num+=n;
		if(n) nn.push_back(r);
	}
	E[cur]=nn;
	
	if(man[cur]) st=cur;
	if((man[cur] || E[cur].size()) && pre>=0) E[cur].push_back(pre);
	
	return num+man[cur];
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>M;
	FOR(i,N-1) {
		cin>>x>>y;
		E[x].push_back(y);
		E[y].push_back(x);
	}
	FOR(i,M) {
		cin>>x;
		man[x]=1;
		st=x;
	}
	if(M==1) return _P("%d\n%d\n",st,0);
	
	prune(st,-1);
	int p=st;
	prune(st,-1);
	
	FOR(i,N) FORR(r,E[i+1]) P++;
	dfs(p,-1);
	dfs2(p,-1,0);
	
	_P("%d\n%d\n",cand,P-ma);
}

まとめ

割と雑に書いたけど本番通ってよかった。