AtCoder ARC #142 : D - Deterministic Placing

過去最悪級だった出来の回。
https://atcoder.jp/contests/arc142/tasks/arc142_d

問題

N頂点からなる木を成す無向グラフが与えられる。
このうち、いくつかの頂点に駒を置くとすると、1個以上駒を置くケースは(2^N-1)通りである。
このグラフにおいて、以下を満たす駒の配置は何通りか。

• 全駒を同時に隣接点に動かす処理を行う。その際、同じ辺を通る駒は1つまでとし、移動後に同じ頂点にいられる駒は1つまでとする。
• 上記処理を繰り返したとき、可能な駒の配置は毎回1通りである。

解法

あるパスにおいて、1つの端点だけ駒がなく、他の点に駒がある状況を考える。
この状態は、明らかに問題の条件を満たす。処理を繰り返しても、毎回駒の行先は固定であり、2つの状態を行き来するだけである。

あとは木DPの要領で、木をパスに分解することを考え、パターンを数え上げる。
各頂点の状態は以下の5通りのいずれかである。

• パスの途中であり、両端がサブツリー内にある
• パスの途中であり、片方の端点がサブツリー内にある
  • うち、サブツリー内にある端点は最初駒がない方である
  • うち、サブツリー内にある端点は最初駒がある方である
• パスの端点の片方である
  • うち、最初駒がない方である
  • うち、最初駒がある方である

このうち親子間で隣接してはいけない状態があるので、それだけ避けて数えていこう。

int N;
vector<int> E[202020];
const ll mo=998244353;
ll dp[202020][5];


void dfs(int cur,int pre) {
	int i,j;
	FORR(e,E[cur]) if(e!=pre) dfs(e,cur);
	
	ll from[4]={1,1,0};
	FORR(e,E[cur]) if(e!=pre) {
		ll to[4]={};
		(to[0]=from[0]*dp[e][2])%=mo;
		(to[1]=from[1]*dp[e][4])%=mo;
		(to[2]=from[2]*dp[e][4]+from[1]*dp[e][0])%=mo;
		swap(from,to);
	}
	dp[cur][0]=dp[cur][1]=(from[0]+from[2])%mo;
	from[0]=1, from[1]=0;
	FORR(e,E[cur]) if(e!=pre) {
		ll to[4]={};
		(to[0]=from[0]*dp[e][3])%=mo;
		(to[1]=from[0]*dp[e][0]+from[1]*dp[e][3])%=mo;
		swap(from,to);
	}
	dp[cur][2]=dp[cur][3]=from[1];
	from[0]=1, from[1]=from[2]=from[3]=0;
	FORR(e,E[cur]) if(e!=pre) {
		ll to[4]={};
		
		(to[0]=from[0]*dp[e][4])%=mo;
		(to[1]=from[0]*dp[e][0]+from[1]*dp[e][4])%=mo;
		(to[2]=from[0]*dp[e][1]+from[2]*dp[e][4])%=mo;
		(to[3]=from[1]*dp[e][1]+from[2]*dp[e][0]+from[3]*dp[e][4])%=mo;
		swap(from,to);
	}
	dp[cur][4]=from[3];
	
	
}

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);
	}
	
	if(N<=2) {
		cout<<2<<endl;
		return;
	}
	FOR(i,N) if(E[i].size()>=2) {
		dfs(i,i);
		ll ret=dp[i][2]+dp[i][3]+dp[i][4];
		cout<<ret%mo<<endl;
		break;
	}
}

まとめ

パスに分ける部分からして思いつかず…。