kmjp's blog

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

AtCoder ARC #022 : C - ロミオとジュリエット

なんでこんなストーリー設定にしたんだろう。
http://arc022.contest.atcoder.jp/tasks/arc022_3

問題

木を成す無向グラフが与えられる。
グラフの直径(2点間の最短路の最長距離)を成す2点を求めよ。

解法

幾つかやり方がある。
以下は自分の本番のやり方を紹介。

適当な点からDFSで求め、候補の点のペアのうち距離が最大のものを求めていく。

  • 答えの2点の間のパスに現在見ている点が含まれる場合:
    • 現在の点の各子について、それぞれ現在の点からの距離が最長のものを探す。上位2点を結んだものが直径候補。
    • 子が1つしかない場合は、現在の点と子の先距離最長の点の対が候補。
  • 答えの2点の間のパスに現在見ている点が含まれない場合:
    • 各子についてそれぞれDFSを行い、子のツリー内で直径候補を求める。

別解として、最遠点を求めるDFSを2回行う手法があるようだ。
こちらはEditorial参照。

int N;
vector<int> E[100001];

int sx,sy;
int ma;

pair<int,int> dfs(int cur,int pre) {
	vector<pair<int,int> > V;
	int i;
	
	FOR(i,E[cur].size()) {
		int tar=E[cur][i];
		if(tar==pre) continue;
		V.push_back(dfs(tar,cur));
	}
	
	V.push_back(make_pair(1,cur));
	
	sort(V.begin(),V.end());
	reverse(V.begin(),V.end());
	if(V.size()>=2) {
		int tar=V[0].first+V[1].first;
		if(tar>ma) {
			ma=tar;
			sx=V[0].second+1;
			sy=V[1].second+1;
		}
	}
	
	return make_pair(V[0].first+1,V[0].second);
}

void solve() {
	int f,i,j,k,l,x,y;
	
	cin>>N;
	FOR(i,N-1) {
		cin>>x>>y;
		E[x-1].push_back(y-1);
		E[y-1].push_back(x-1);
	}
	
	dfs(0,-1);
	_P("%d %d\n",sx,sy);
}

まとめ

最遠点を2回求める方法は知らなかった…。