kmjp's blog

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

天下一プログラマーコンテスト2015 本戦(オープン) : F - 根付き木のみさわさん

難易度がC>>E>Fだと感じたし、正答数もそんなもんだけどなぜこの3問が150,140,130点なんだろうな。
http://tenka1-2015-final-open.contest.atcoder.jp/tasks/tenka1_2015_final_f

問題

N頂点の根付き木がある。

この木に対し、以下のクエリがQ個与えられるのでそれぞれ答えよ。

  • 木中M個の頂点に実がなっている。subtreeにK個以上の実があるような頂点のうち、最も深い(根から遠い)頂点の深さを求めよ。

解法

Euler-Tour+LCAで解ける。

Euler-Tourの要領で、各頂点にDFS到達順で連番を付けておく。
またLCAを計算できるよう親のダブリングを済ませておく。

各クエリに対し、実のなる頂点をDFS到達順でソートした配列をVとする。
そしてLCA(V[i],V[i+K-1])が最も深い頂点を求め、その深さを返せばよい。

int N,Q,M,K;
vector<int> E[101010];
int P[21][101010],D[100005];
int L[101010],R[101010],idt[101010];
int id=1;

void dfs(int cur,int pre) {
	int i,p=-1;
	if(pre!=-1) D[cur]=D[pre]+1;
	
	P[0][cur]=pre;
	idt[id]=cur;
	L[cur]=id++;
	FOR(i,E[cur].size()) {
		int tar=E[cur][i];
		if(tar==pre) p=i;
		else dfs(tar,cur);
	}
	R[cur]=id;
	if(p>=0) E[cur].erase(E[cur].begin()+p);
}

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
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	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);
	FOR(i,19) FOR(x,N) P[i+1][x]=P[i][P[i][x]];
	
	cin>>Q;
	while(Q--) {
		cin>>M>>K;
		vector<int> v;
		while(M--) {
			cin>>x;
			v.push_back(L[x-1]);
		}
		sort(v.begin(),v.end());
		int mad=0;
		for(i=0;i+K-1<v.size();i++) {
			x=idt[v[i]];
			y=idt[v[i+K-1]];
			
			mad=max(mad,D[lca(x,y)]);
		}
		cout<<mad<<endl;
		
	}

}

まとめ

これはほとんど方針迷わなかったし、実際本番10分足らずで解いてる。
もう少し配点低くても良さそうだけど…CやEにもっと簡潔な解法があったりした?