Polynomial Round 2022 : E. Two Chess Pieces

Hackですごく稼いだ回。
https://codeforces.com/contest/1774/problem/E

問題

根付き木が与えられる。
初期状態で2つの駒が根頂点にある。

両駒それぞれ訪問すべき点の集合が与えられる。
順序はどうでもよいので、任意の駒を隣接点に動かすことを繰り返し、両駒それぞれ訪問すべき点をすべて通って元の根頂点に戻したい。
ただいし、両駒の距離がDを超えてはならない。

最小の手順を求めよ。

解法

「片方の駒が点vを訪問しなければならないなら、もう片方の駒はそのD個親側の点を訪問しなければならない」
という条件を考えると、両駒が訪問すべき点が列挙できる。

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

int A[2][202020];

void dfs(int cur) {
	FORR(e,E[cur]) if(e!=P[0][cur]) D[e]=D[cur]+1, P[0][e]=cur, dfs(e);
}
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 dfs2(int cur) {
	FORR(e,E[cur]) if(e!=P[0][cur]) D[e]=D[cur]+1, P[0][e]=cur, dfs2(e);
	if(A[0][cur]) A[0][P[0][cur]]=1;
	if(A[1][cur]) A[1][P[0][cur]]=1;
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>SD;
	FOR(i,N-1) {
		cin>>x>>y;
		E[x-1].push_back(y-1);
		E[y-1].push_back(x-1);
	}

	//0以外を根にするならP[0][root]=rootが必要
	dfs(0);
	FOR(i,19) FOR(x,N) P[i+1][x]=P[i][P[i][x]];
	
	FOR(j,2) {
		cin>>x;
		FOR(i,x) {
			cin>>y;
			y--;
			A[j][y]=1;
			A[j^1][getpar(y,SD)]=1;
		}
	}
	dfs2(0);
	int ret=0;
	FOR(i,N) if(i) {
		if(A[0][i]) ret+=2;
		if(A[1][i]) ret+=2;
	}
	cout<<ret<<endl;
}

まとめ

本番やけにあっさり解けたな。