kmjp's blog

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

Codeforces ECR #062 : G. Double Tree

Codeforces

これまた実装が重い。
https://codeforces.com/contest/1140/problem/G

問題

2N頂点からなる距離付の無向グラフが与えられる。
頂点番号が0-indexであるとすると、(2k,2k+1)の頂点が組であるとする。
N個の組の間は互いに辺が張られている。
また、奇数番の頂点群と偶数番の頂点群はそれぞれ互いに(N-1)本の辺をもち木を成している。
この木の形状は両者同じであるが、距離は異なっている。

このような形状のグラフにおいて、２頂点からなるクエリがQ個与えられるので、それぞれパスの最短路を求めよ。

解法

もし奇数番・偶数番の間をつなぐ辺は置いておいて、２つの木を構成する辺を考える。
この辺の移動回数を最小にするならば、重心(正確には両方の木の重心の２頂点)をまたぐ頂点間の最短距離は重心分解の要領で処理できる。

ただ、今回の場合では奇数番と偶数番の頂点間を行き来するために、重心をまたがなくても到達できる場合でも、重心をこえて奇数番と偶数番の頂点間を行き来した後戻ってくる方が距離が下がる場合がある。

よって、先に後者を解決しておこう。
すなわち、(2k,2k+1)間の最短距離を先に列挙しておく。
そうすればあとは重心分解で応えられる。

(2k,2k+1)間の最短距離を求めるため、以下のような(N+1)頂点のグラフを考える。

  • もともと組である頂点対に対応して、対に対し頂点を1個作る。
    • このN頂点において、元のグラフで辺がある場合、新しいグラフでも辺を張る。この時、頂点間の距離は奇数同士の頂点間の距離と、偶数同士の頂点間の距離の和とする。
  • さらに、初期位置に相当する点を1個作る。この点から先のN点に辺を張る。この時その距離は元のグラフにおける対の間の辺の距離である。

このグラフにおいて、初期位置からの距離を列挙すると、それは(2k,2k+1)間の最短距離となる。
これは奇数・偶数頂点対の間を移動するためにどこか遠くに行って戻ってくるなら、２つの木それぞれにおいてそこまでいくだけの距離が必要となるためである。

int N;
ll OE[303030];
int X[303030],Y[303030];
ll OO[303030],EE[303030];

vector<pair<int,ll>> E[303030];
vector<pair<int,ll>> E2[603030];
ll D[303030];
ll D2[603030][2];
int Q;
ll U[606060],V[606060];
ll ret[606060];

int vis[301010],id[303030];
int NV[301010];

int dfs(int cur,int pre) {
	NV[cur]=1;
	FORR(e,E[cur]) if(e.first!=pre && vis[e.first]==0) NV[cur]+=dfs(e.first,cur);
	D2[cur*2][0]=D2[cur*2][1]=D2[cur*2+1][0]=D2[cur*2+1][1]=1LL<<60;
	return NV[cur];
}

int dfs2(int cur,int pre,int TNV) {
	int tot=1;
	int ok=1;
	FORR(e,E[cur]) if(e.first!=pre && vis[e.first]==0) {
		int c = dfs2(e.first,cur,TNV);
		if(c!=-1) return c;
		tot += NV[e.first];
		if(NV[e.first]*2>TNV) ok=0;
	}
	if((TNV-tot)*2>TNV) ok=0;
	if(ok) return cur;
	return -1;
}

void dfs3(int cur,int pre,int col) {
	id[cur]=col;
	FORR(e,E[cur]) if(e.first!=pre && vis[e.first]==0) dfs3(e.first,cur,col);
}
	

void split(int cur,vector<int>& C) {
	if(vis[cur] || C.empty()) return;
	int TNV = dfs(cur,-1);
	if(TNV==0) return;
	int center=dfs2(cur,-1,TNV);
	vis[center]=1;
	
	vector<vector<int>> cand(E[center].size());
	int i;
	FOR(i,E[center].size()) if(vis[E[center][i].first]==0) dfs3(E[center][i].first,center,i);
	id[center]=-1;
	
	D2[center*2][0]=D2[center*2+1][1]=0;
	priority_queue<pair<ll,int>> PQ;
	PQ.push({0,center*2*2});
	PQ.push({0,(center*2+1)*2+1});
	while(PQ.size()) {
		ll co=-PQ.top().first;
		int cur=PQ.top().second/2;
		int t=PQ.top().second%2;
		PQ.pop();
		if(D2[cur][t]!=co) continue;
		FORR(e,E2[cur]) if(D2[e.first][t]>co+e.second) {
			D2[e.first][t]=co+e.second;
			PQ.push({-D2[e.first][t], e.first*2+t});
		}
	}
	
	FORR(c,C) {
		if(id[U[c]/2]==id[V[c]/2] && id[U[c]/2]!=-1) {
			cand[id[U[c]/2]].push_back(c);
		}
		else {
			ret[c]=min(D2[U[c]][0]+D2[V[c]][0],D2[U[c]][1]+D2[V[c]][1]);
		}
	}
	
	
	
	FOR(i,E[center].size()) if(vis[E[center][i].first]==0) split(E[center][i].first,cand[i]);
	
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N) cin>>OE[i];
	FOR(i,N-1) {
		cin>>X[i]>>Y[i]>>OO[i]>>EE[i];
		X[i]--;
		Y[i]--;
		E2[X[i]*2].push_back({Y[i]*2,OO[i]});
		E2[Y[i]*2].push_back({X[i]*2,OO[i]});
		E2[X[i]*2+1].push_back({Y[i]*2+1,EE[i]});
		E2[Y[i]*2+1].push_back({X[i]*2+1,EE[i]});
	}
	
	FOR(i,N) {
		E[N].push_back({i,OE[i]});
		D[i]=1LL<<60;
	}
	FOR(i,N-1) {
		E[X[i]].push_back({Y[i],OO[i]+EE[i]});
		E[Y[i]].push_back({X[i],OO[i]+EE[i]});
	}
	priority_queue<pair<ll,int>> PQ;
	PQ.push({0,N});
	while(PQ.size()) {
		ll co=-PQ.top().first;
		int cur=PQ.top().second;
		PQ.pop();
		
		if(D[cur]!=co) continue;
		FORR(e,E[cur]) if(D[e.first]>co+e.second) {
			D[e.first]=co+e.second;
			PQ.push({-D[e.first],e.first});
		}
	}
	
	FOR(i,N) {
		OE[i]=min(OE[i],D[i]);
		E2[i*2].push_back({i*2+1,OE[i]});
		E2[i*2+1].push_back({i*2,OE[i]});
	}
	
	cin>>Q;
	vector<int> cand;
	FOR(i,Q) {
		cin>>U[i]>>V[i];
		U[i]--,V[i]--;
		cand.push_back(i);
	}
	
	split(0,cand);
	
	FOR(i,Q) cout<<ret[i]<<endl;
	
	
	
	
}

まとめ

ダイクストラやって重心分解やって…と非常に面倒。
こんなの思いつかないわ…。