yukicoder : No.768 Tapris and Noel play the game on Treeone

全方位DPの典型のような問題。
https://yukicoder.me/problems/no/768

問題

N頂点からなる木を成す無向グラフが与えられる。
２人で交互に以下のゲームを行う。

• 先手は任意の頂点に文字を書く。
• 以後の手番では、前の人が文字を書いた頂点に隣接する、文字が書かれていない頂点を１つ選び文字を書く。
• 自分の手番で文字を書けなくなったら負け。

先手必勝となる頂点を列挙せよ。

解法

最初の頂点を定めたとすると、木の根をその頂点とする根付き木を考えると、両者の手番は木の根から順に子のいずれかに移動することになる。
よって、DFS等で各頂点「相手が必敗の子頂点があれば必勝」というのを葉側から順次行っていけばよい。

あとは、根を総当たりして同様の手順を繰り返す。
ただ当然愚直に行うとO(N^2)かかるので、現在の頂点と親頂点をキーとしてメモ化再帰しよう。
ある頂点にK個隣接点があるとき、親頂点と子頂点の組み合わせによりその頂点でO(K^2)回の処理が必要になるので、グラフの形状によってはTLEする。
ただ、必敗の隣接点数を一旦数えてしまえば、親頂点分を必敗かどうか引けばよくなるので計算量を抑えることができる。

int N;
vector<int> E[101010];
map<int,int> memo[101010];

int win(int cur,int pre) {
	if(memo[cur].count(pre)) return memo[cur][pre]==0;
	
	int ng=0;
	if(memo[cur].size()) {
		auto a=memo[cur].begin();
		ng=a->second;
		if(a->first>=0) ng+=win(a->first,cur);
		if(pre!=-1) ng-=win(pre,cur);
	}
	else {
		FORR(e,E[cur]) if(e!=pre) ng+=win(e,cur);
	}
	
	return (memo[cur][pre]=ng)==0;
}

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);
	}
	vector<int> R;
	FOR(i,N) if(win(i,-1)) R.push_back(i+1);
	cout<<R.size()<<endl;
	FORR(r,R) cout<<r<<endl;
}

まとめ

★3.5ぐらいでもいい気がするな。
全方位木DPに苦手意識のある人が多いのかな。