kmjp's blog

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

Codeforces ECR #053 : F. Choosing Two Paths

Codeforces

実装が間に合わず…。
http://codeforces.com/contest/1073/problem/F

問題

木を成す無向グラフが与えられる。
２つのパスの対のうち、以下を満たすものの１例を答えよ。

  • パスの両端が、もう一つのパス上に来ない
  • パスの共通部分の長さが、あり得るものの中で最長
  • 上記条件が一致するものが複数ある場合、パスの総長が最長

解法

パスの共通部分がU,Vであるとき、U,Vの次数が３以上であることが必須条件である。
そこで、条件を満たすような頂点およびそれらをつなぐパスで構成されたグラフを作ろう。
これは条件を満たさない次数２以下の頂点を葉から順に削除していけば構成できる。

このグラフで直径を成す２点を求めればそれがU,Vの候補となる。
そこで、このグラフの中心からDFSしていき、次数３以上の頂点のうち最も中心からの距離が遠いものと、さらにその先の（元のグラフの）葉のうち中心からの距離が遠い上位２つを求めよう。

最終的に、中心から見て各子頂点の先にある「次数３以上の頂点のうち最も中心からの距離が遠いもの」および「その先の（元のグラフの）葉のうち中心からの距離が遠い上位２つ」の上位２つを求めて４つの葉を両端とするパスを２つ作ろう。

以下のコードでは、頂点を倍加して必ず直径が偶数になるようにしている。

int N;
vector<int> E[401010];
set<int> SE[401010];
int FD[402020],D[402020],CD[402020];
vector<pair<int,int>> MD[402020];
int nodel[404040];

int DD,D2;
vector<int> C;

void dfs(int cur,int pre) {
	if(pre!=-1) D[cur]=D[pre]+1;
	int i;
	FOR(i,E[cur].size()) {
		if(E[cur][i]==pre) {
			E[cur].erase(E[cur].begin()+i);
			break;
		}
	}
	
	
	CD[cur]=-1;
	if(E[cur].size()==0) {
		MD[cur].push_back({D[cur],cur});
	}
	else if(E[cur].size()==1) {
		FORR(e,E[cur]) {
			dfs(e,cur);
			CD[cur]=CD[e];
			MD[cur]=MD[e];
		}
	}
	else {
		vector<vector<int>> cand;
		FORR(e,E[cur]) {
			dfs(e,cur);
			if(CD[e]>=0) cand.push_back({D[CD[e]],MD[e][0].first+MD[e][1].first-2*D[CD[e]],e});
		}
		
		sort(ALL(cand));
		reverse(ALL(cand));
		if(cand.size()>=2) {
			int len=cand[0][0]+cand[1][0]-2*D[cur];
			int slen=cand[0][1]+cand[1][1];
			
			if(len>DD || (len==DD && slen>D2)) {
				DD=len;
				D2=slen;
				C.clear();
				C.push_back(MD[cand[0][2]][0].second+1);
				C.push_back(MD[cand[1][2]][0].second+1);
				C.push_back(MD[cand[0][2]][1].second+1);
				C.push_back(MD[cand[1][2]][1].second+1);
			}
			
		}
		if(cand.size()>=1) {
			CD[cur]=CD[cand[0][2]];
			MD[cur]=MD[cand[0][2]];
		}
		else {
			CD[cur]=cur;
			FORR(e,E[cur]) MD[cur].push_back(MD[e][0]);
			sort(ALL(MD[cur]));
			reverse(ALL(MD[cur]));
			MD[cur].resize(2);
		}
	}
}

pair<int,int> farthest(int cur,int pre,int d,vector<int>& D) {
	D[cur]=d;
	pair<int,int> r={d,cur};
	FORR(e,SE[cur]) if(e!=pre) r=max(r, farthest(e,cur,d+1,D));
	return r;
}

//両端と間の頂点を返す
int diameter(int S) { // diameter,center
	vector<int> D[2];
	D[0].resize(N);
	D[1].resize(N);
	auto v1=farthest(S,0,0,D[0]);
	auto v2=farthest(v1.second,v1.second,0,D[0]);
	farthest(v2.second,v2.second,0,D[1]);
	
	vector<pair<int,int>> R;
	//重心を取る場合
	int i;
	FOR(i,N) if(SE[i].size() && D[0][i]+D[1][i]==v2.first) R.push_back({D[0][i],i});
	sort(ALL(R));
	return R[R.size()/2].second;
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	int nex=N;
	FOR(i,N-1) {
		cin>>x>>y;
		E[x-1].push_back(nex);
		E[nex].push_back(x-1);
		E[y-1].push_back(nex);
		E[nex].push_back(y-1);
		SE[x-1].insert(nex);
		SE[nex].insert(x-1);
		SE[y-1].insert(nex);
		SE[nex].insert(y-1);
		nex++;
	}
	N=nex;
	queue<int> Q;
	int R;
	FOR(i,N) {
		if(E[i].size()>=3) nodel[i]=1, R=i;
		if(E[i].size()==1) Q.push(i);
	}
	while(Q.size()) {
		x=Q.front();
		Q.pop();
		FORR(e,SE[x]) {
			SE[e].erase(x);
			if(nodel[e]==0 && SE[e].size()==1) Q.push(e);
		}
		SE[x].clear();
	}
	R=diameter(R);
	
	dfs(R,-1);
	cout<<C[0]<<" "<<C[1]<<endl;
	cout<<C[2]<<" "<<C[3]<<endl;
	
}

まとめ

うーん、考察はともかく実装が面倒な問題。