AtCoder ARC #121 (NOMURA プログラミングコンテスト 2021) : F - Logical Operations on Tree

これは落ち着いて解けば、自力で行けたかもな…。
https://atcoder.jp/contests/arc121/tasks/arc121_f

問題

木を成すN頂点のグラフが与えられる。
各頂点に0/1のいずれか、そして各辺にAND/ORのいずれかを付与することを考える。
付与の仕方は2^(2N-1)通りである。

そのうち、以下の条件を満たすものは何通りか。

• 辺を1つ選び、両端の頂点を縮約することを考える。縮約後の頂点の値は、元の両端の頂点の値に、辺に付与された演算を施すことで得られる。
• 任意の順に辺を選ぶとき、最後に残った点の値が1である。

解法

• 葉の値が1で、そこにORの辺がついているとき、この辺を最後に処理すれば必ず最後の点は1になる。
• 葉の値が1で、そこにANDの辺がついているとき、この辺はいつ処理しても以後影響を与えない(ので無視してよい)
• 葉の値が0で、そこにORの辺がついているとき、この辺はいつ処理しても以後影響を与えない(ので無視してよい)
• 葉の値が0で、そこにANDの辺がついているとき、さっさとこの辺を適用してしまった方が良い。

とすると、SubTree毎に以下の各状態における組み合わせを求めよう。

• 「葉の値が1で、そこにORの辺がついている」状態を含む。つまり条件達成確定済み。
• 確定済みではない場合：
  • SubTreeを上記手順で処理すると、0が残る
  • SubTreeを上記手順で処理すると、1が残る

最終的に、確定済みの部分を含むか、根頂点に1が残るようになる組み合わせが解の対象となる。

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

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

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	if(N==2) {
		cout<<4<<endl;
		return;
	}
	FOR(i,N-1) {
		cin>>x>>y;
		E[x-1].push_back(y-1);
		E[y-1].push_back(x-1);
	}
	FOR(i,N) if(E[i].size()>1) break;
	dfs(i,i);
	cout<<(dp[i][2]+dp[i][1])%mo<<endl;
		
}

まとめ

最近のARCの中ではおとなしい。