AtCoder ABC #223 : G - Vertex Deletion

まぁGはどうにか。
https://atcoder.jp/contests/abc223/tasks/abc223_g

問題

木を成す無向グラフが与えられる。
各頂点(及びそこにつながる辺)を除いた時、その残余グラフにおける最大マッチングと元のグラフの最大マッチングの数が一致する頂点は何通りか。

解法

頑張って全方位木DPを行う問題。
各頂点vについて、
f(v) := vのsubtreeで構成されるマッチングのうち、vをマッチングに含むケースの最大値
g(v) := vのsubtreeで構成されるマッチングのうち、vをマッチングに含まないケースの最大値
をDFSで求め、その後逆に親側から親側の値を反映させていこう。

int N;
vector<int> E[202020];
int dp[202020][2];
int P[202020];
int tar;
int ret;
void dfs(int cur,int pre) {
	int from[2]={0,0};
	P[cur]=pre;
	FORR(e,E[cur]) if(e!=pre) {
		dfs(e,cur);
		int to[2];
		
		to[0]=from[0]+max(dp[e][0],dp[e][1]);
		to[1]=max({from[0]+dp[e][0]+1,from[1]+dp[e][0],from[1]+dp[e][1]});
		swap(from,to);
	}
	dp[cur][0]=from[0];
	dp[cur][1]=from[1];
}

void dfs2(int cur,int pre,int a0,int a1) {
	int ma=max(a0,a1);
	set<int> cand;
	if(a0==a1) cand.insert(pre);
	FORR(e,E[cur]) if(e!=pre) {
		ma+=max(dp[e][0],dp[e][1]);
		if(dp[e][0]==dp[e][1]) cand.insert(e);
	}
	if(ma==tar) ret++;
	FORR(e,E[cur]) if(e!=pre) {
		int pa=ma-max(dp[e][0],dp[e][1]);
		if(cand.count(e)!=cand.size()) dfs2(e,cur,pa,pa+1);
		else dfs2(e,cur,pa,pa);
	}
}

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,0);
	tar=max(dp[0][0],dp[0][1]);
	dfs2(0,0,-1<<20,0);

	cout<<ret<<endl;
}

まとめ

解法はすぐ思いつくけど、細かいところを詰めるのが面倒な問題。