CF461B Appleman and Tree 的题解

状态挺神奇的。

考虑设

f_{u,0/1}

在以

u

为根的子树中，点

u

在没有黑点的连通块内或有且仅有一个黑点的联通块内的方案数。

那么在合并儿子节点时，设

v

是

u

的儿子节点，有方程：

\begin{cases} f_{u,1} &\larr f_{u,1} \times f_{v,0} + f_{u,1} \times f_{v,1} + f_{u,0} \times f_{v,1}\\ f_{u,0} &\larr f_{u,0} \times f_{v,0} + f_{u,0} \times f_{v,1} \end{cases}

初始化为

f_{u,col_u} = 1

。

实质上就是枚举了

u,v

之间的边的联通情况对答案的影响。

状态清奇，好思路。

code

CPP

#include<bits/stdc++.h>
#define endl '\n'
//#define MSOD

using namespace std;
using ll = long long;
constexpr ll N = 1e5 + 5, M = 1e9 + 7;

ll n;
ll dp[N][2];
bool col[N];
vector<ll> g[N];
inline void dfs(ll u, ll dad) {
	for(auto v : g[u]) {
		if(v == dad) {
			continue;
		}
		dfs(v, u);
		dp[u][1] = dp[u][1] * dp[v][0] % M + dp[u][1] * dp[v][1] % M + dp[u][0] * dp[v][1] % M;
		dp[u][0] = dp[u][0] * dp[v][0] % M + dp[u][0] * dp[v][1] % M;
		dp[u][1] %= M, dp[u][0] %= M;
	}
	return;
}
inline void solve() {
	cin>>n;
	for(int i = 0 ; i < n - 1 ; i ++) {
		ll x;
		cin>>x;
		g[x].push_back(i + 1), g[i + 1].push_back(x); 
	}
	for(int i = 0 ; i < n ; i ++) {
		cin>>col[i];
		dp[i][col[i]] = 1;
	}
	dfs(0, -1);
	cout<<dp[0][1];
	return;
}

signed main() {
	ios::sync_with_stdio(false), cout.tie(0), cin.tie(0);
	int TC = 1;
#ifdef MSOD
	cin>>TC;
#endif
	while(TC --) {
		solve();
	}
	return 0;
}

CF461B Appleman and Tree 的题解

文章操作

相关推荐

评论

CF461B Appleman and Tree 的题解