kmjp's blog

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

Codeforces #339 Div1. D. Kingdom and its Cities

Codeforces

一応本番中に思いついた方針で後日最終的に自力で解いたけど、バグらせまくりで到底時間内には間に合わなかった。
http://codeforces.com/contest/613/problem/D

問題

N頂点からなる木を成すグラフが与えられる。

このグラフに対しQ個のクエリに解答せよ。
各クエリでは、N頂点中いくつか重要な頂点が指定される。
いくつかの(重要でない)頂点を塞ぐことで、重要な頂点同士が辺を辿って到達できないようにしたい。
各クエリについて、塞ぐべき最少頂点数を求めよ。

解法

まず木を根付き木とし、EulerTourで順序付けした上で、LCAを求められるよう前処理しておく。

各クエリについて、まず重要な頂点をEulerTour順にソートしよう。
これらの頂点列について、以下の処理を行う。

  • (頂点列中で)隣接する頂点同士のLCAを求め、一番深いものを求める。
  • その隣接点同士が重要な点に接続されているなら、このLCAは塞ぐべきである。そうでないなら塞がなくてよい。
  • 塞ぐにせよ塞がないにせよ、そのLCAのSubTree中にLCAに到達可能な頂点が0個か1個かを順次更新する。そして頂点列中の処理した２つの隣接点をLCAで置き換える。

上記処理を頂点が1個になるまで行う。
LCAの深さ順ソートはsetで行えば間に合う。
数列中で隣接する２点をLCAに置き換える、という処理は、双方向リンクリストを用いれば高速に数列の要素削減ができる。

注意点として、LCAがすでに重要な点の場合、そこを塞ぐことができない。
例えば(頂点列中で)隣接する2頂点をx,yとしたとき、xがyの祖先でかつxが重要な場合、xとyの距離が2以上あれば間の頂点を塞げばよい。
yがxの個であると塞げないので、条件を満たす塞ぎ方はできない。

const int ME=300005;
vector<int> LL[ME];
int L[ME],R[ME],eid;
int ST[ME];

int N,Q,K;
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
}

void EulerTour(int cur,int pre=-1) {
	int i;
	FOR(i,E[cur].size()) if(E[cur][i]==pre) {
		E[cur].erase(E[cur].begin()+i);
		break;
	}
	L[cur]=eid++;
	ITR(it,E[cur]) {
		EulerTour(*it,cur);
		LL[cur].push_back(L[*it]);
	}
	R[cur]=eid;
}

int hoge(vector<int>& V,int st) {
	
	int i,N;
	N=V.size();
	
	vector<pair<int,int>> VV;
	FORR(r,V) VV.push_back({L[r],r});
	sort(VV.begin(),VV.end());
	FOR(i,N) V[i]=VV[i].second;
	
	set<pair<int,int>> Q;
	FOR(i,N-1) Q.insert({-D[lca(V[i],V[i+1])],i});

	vector<pair<int,int>> nex;
	FOR(i,N) nex.push_back({i-1,i+1});
	nex[0].first=0;
	nex[N-1].second=N-1;
	
	int cost=0;
	while(Q.size()) {
		auto r=*Q.begin();
		Q.erase(Q.begin());
		
		int x=r.second;
		int y=nex[x].second;
		
		if(x!=nex[x].first) Q.erase({-D[lca(V[x],V[nex[x].first])],nex[x].first});
		if(y!=nex[y].second) Q.erase({-D[lca(V[y],V[nex[y].second])],y});
		
		int lc=lca(V[x],V[y]);
		if(abs(ST[lc])<st) ST[lc]=0;
		if(ST[V[x]]==st && ST[V[y]]==st && P[0][V[y]]==V[x]) return -1;
		if(ST[V[x]]>=st && ST[V[y]]>=st) cost++;
		
		if(ST[lc]==0 || ST[lc]%2) {
			if(ST[V[x]]>0 && ST[V[y]]>0) ST[lc]=-st;
			else if(ST[V[x]]<0 && ST[V[y]]<0) ST[lc]=-st-1;
			else ST[lc]=st+1;
		}
		
		V[x]=lc;
		if(x!=nex[x].first) Q.insert({-D[lca(V[x],V[nex[x].first])],nex[x].first});
		if(y!=nex[y].second) {
			nex[nex[y].second].first=x;
			nex[x].second=nex[y].second;
			Q.insert({-D[lca(V[x],V[nex[y].second])],x});
		}
		else nex[x].second=x;
	}
	
	return cost;
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	int go=0;
	cin>>N;
	FOR(i,N-1) {
		cin>>x>>y;
		if(i==0 && x==2) go=1;
		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]];
	EulerTour(0);
	
	cin>>Q;
	int st;
	FOR(st,Q) {
		cin>>K;
		vector<int> V;
		FOR(i,K) cin>>x, x--, V.push_back(x), ST[x]=(st+1)*2;
		
		cout<<hoge(V,(st+1)*2)<<endl;
	}
	
}

まとめ

双方向リンクリストと、LCAの深さ順に処理する方針はすぐ立ったけど、後の頂点の状態遷移に大混乱。