Good Bye 2024: 2025 is NEAR : E. Resourceful Caterpillar Sequence

一見複雑そうで実際はシンプル。
https://codeforces.com/contest/2053/problem/E

問題

根付き木が与えられる。
ここで、初期状態でパス(p,q)からなるキャタピラを考える。

これを用いて2人でターン制のゲームを行う。

• 先手は、pと隣接する点を選び、キャタピラ全体をそちらに引っ張る
• 後手は、qと隣接する点を選び、キャタピラ全体をそちらに引っ張る

途中p,qのいずれかが葉に到達したら、それぞれ先手・後手が勝ちとなる。
最適手を取ったとき、後手が勝ちとなる初期状態は何通りか。

解法

最初からpが葉になく、qが葉であるときは後手が勝つ。
あとは、pが1手で勝てず、qが1手先手に引っ張られたときに、後手が1手で葉に到達できるような(p,q)を数え上げよう。

各辺を総当たりし、それぞれ先手の移動前後である場合、先手が1手で葉に到達できず、後手が1手で葉に到達できるケースを数えるとよい。
これらはDFS訪問順の頂点の並べ替えと、葉の個数の累積和を使うと、1辺あたりO(1)で数えられる。

int T,N;
vector<int> E[202020];
int ok[202020];
int S[202020];
const int ME=202020;
int L[ME],R[ME],D[ME],P[ME],rev[ME];


void EulerTour(int cur,int pre=-1,int d=0) {
	static int eid;
	if(pre==-1) eid=1, pre=0;
	rev[eid]=cur;
	P[cur]=pre;
	L[cur]=eid++;
	D[cur]=d;
	FORR(e,E[cur]) if(e!=pre) EulerTour(e,cur,d+1);
	R[cur]=eid;
}



void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>T;
	while(T--) {
		cin>>N;
		FOR(i,N+5) E[i].clear(),S[i]=0;
		FOR(i,N-1) {
			cin>>x>>y;
			E[x-1].push_back(y-1);
			E[y-1].push_back(x-1);
		}
		int leaf=0;
		FOR(i,N) if(E[i].size()==1) leaf++;
		ll ret=0;
		//すでにqがleaf
		ret+=1LL*leaf*(N-leaf);
		
		EulerTour(0);
		
		FOR(i,N) {
			if(E[i].size()==1) {
				D[i]=0;
			}
			else {
				D[i]=2;
				FORR(e,E[i]) if(E[e].size()==1) D[i]=1;
			}
			S[L[i]]=D[i]==2;
		}
		FOR(i,N+2) S[i+1]+=S[i];
		
		FOR(i,N) FORR(e,E[i]) if(D[i]&&D[e]==1) {
			if(L[i]<L[e]) {
				ret+=S[R[e]-1]-S[L[e]-1];
			}
			else {
				ret+=S[L[i]-1];
				ret+=S[N]-S[R[i]-1];
			}
		}
		
		
		cout<<ret<<endl;
	}
}

まとめ

これはまぁまぁの時間で解けていた。