kmjp's blog

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

Codeforces #425 Div2 D. Misha, Grisha and Underground

このテクは覚えておくか。
http://codeforces.com/contest/832/problem/D

問題

木を成すグラフに対し、以下のクエリに答えよ。

  • 3頂点A,B,Cが指定される。これらをS,T,Fとそれぞれ1対1に対応付けたとする(対応付けは任意である)
  • この時、パスS→TとF→Tのうち両方のパスが通過する頂点数の最大値を求めよ。

解法

パスAB,BC,CAがすべて通る点をDとする。
この時、求める値はmax(|AD|,|BD|,|CD|)+1である。

厳密にLCA等使いDを求めてもよいが、max(|AD|,|BD|,|CD|)はもっと簡単に求めることができる。
AB,BC,CAの長さを短い順にL1,L2,L3とすると、(L2+L3-L1)/2がそれに対応する。

int N,Q;
vector<int> E[200005];
int P[21][200005],D[200005];

void dfs(int cur) {
	ITR(it,E[cur]) if(*it!=P[0][cur]) D[*it]=D[cur]+1, P[0][*it]=cur, dfs(*it);
}
int lca(int a,int b) {
	int ret=0,i,aa=a,bb=b;
	if(D[aa]>D[bb]) swap(aa,bb);
	for(i=19;i>=0;i--) if(D[bb]-D[aa]>=1<<i) bb=P[i][bb];
	for(i=19;i>=0;i--) if(P[i][aa]!=P[i][bb]) aa=P[i][aa], bb=P[i][bb];
	return (aa==bb)?aa:P[0][aa];               // vertex
}

int dist(int a,int b) {
	return D[a]+D[b]-2*D[lca(a,b)];
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>Q;
	FOR(i,N-1) {
		cin>>x;
		E[i+1].push_back(x-1);
		E[x-1].push_back(i+1);
	}
	dfs(0);
	FOR(i,19) FOR(x,N) P[i+1][x]=P[i][P[i][x]];
	
	while(Q--) {
		int A,B,C;
		cin>>A>>B>>C;
		A--,B--,C--;
		int AB=dist(A,B);
		int BC=dist(B,C);
		int CA=dist(C,A);
		
		cout<<(AB+BC+CA-2*min({AB,BC,CA}))/2+1<<endl;
		
	}
	
	
}

まとめ

本番一応AC出たけどLCAでぐだぐだやってしまった。
このテクは覚えておこう。