CSAcademy Round #30 : E. Triplet Min Sum

方針はすぐ立ったのに、余計なことして3分ぐらいロスした。
https://csacademy.com/contest/round-30/task/triplet-min-sum/

問題

木を成すグラフが与えられる。
以下のクエリに答えよ。

• 頂点A,B,Cが指定される。頂点Dのうち、D-A,D-B,D-C間の距離の総和が最小となるものを求め、総和とともに答えよ。

解法

Dの候補はLCA(A,B),LCA(A,C),LCA(B,C)のいずれかなので、3通り試して距離の最小値を取ればよい。

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 getpar(int cur,int up) {
	int i;
	FOR(i,20) if(up&(1<<i)) cur=P[i][cur];
	return cur;
}

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
}

pair<int,int> hoge(int a,int b,int c) {
	int ret=0;
	int x=lca(a,b);
	ret = D[a]-D[x]+D[b]-D[x];
	int y=lca(x,c);
	ret += D[c]-D[y]+D[x]-D[y];
	return {ret,x};
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>Q;
	FOR(i,N-1) {
		cin>>x>>y;
		E[x-1].push_back(y-1);
		E[y-1].push_back(x-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--;
		pair<int,int> ret={1<<30,0};
		ret=min(ret,hoge(a,b,c));
		ret=min(ret,hoge(a,c,b));
		ret=min(ret,hoge(b,c,a));
		cout<<ret.second+1<<" "<<ret.first<<endl;
	}
	
}

まとめ

ミスなく書けるようになりたい。