[nk] 牛客练习赛97 D.月之暗面 树形dp记录方案数

前言

传送门 :

题意

思路

一眼题了属于是,第一次碰到树形 d p dp dp 记录方案数记录一下

状态表示 : d p [ i ] [ 0 ] dp[i][0] dp[i][0]表示当前节点使用普通颜色 d p [ i ] [ 1 ] dp[i][1] dp[i][1]表示当前节点使用特殊颜色

状态转移 : 同上司的舞会, d p [ u ] [ 0 ] = d p [ u ] [ 0 ] ∗ ( d p [ x ] [ 0 ] + d p [ x ] [ 1 ] ∗ y % m o d ) % m o d ; dp[u][0] = dp[u][0]*(dp[x][0]+dp[x][1]*y\%mod)\%mod; dp[u][0]=dp[u][0]∗(dp[x][0]+dp[x][1]∗y%mod)%mod; d p [ u ] [ 1 ] = d p [ u ] [ 1 ] ∗ ( d p [ x ] [ 0 ] + d p [ x ] [ 1 ] ∗ ( y − 1 ) % m o d ) % m o d ; dp[u][1] = dp[u][1]*(dp[x][0]+dp[x][1]*(y-1)\%mod)\%mod; dp[u][1]=dp[u][1]∗(dp[x][0]+dp[x][1]∗(y−1)%mod)%mod;

Mycode

#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
#define IOS  ios::sync_with_stdio(false);
#define CIT  cin.tie(0);
#define COT  cout.tie(0);

#define ll long long
#define x first
#define y second
#define pb push_back
#define endl '\n'
#define all(x) (x).begin(),x.end()
#define Fup(i,a,b) for(int i=a;i=b;i--)

typedef priority_queue  Pri_m;
typedef pair pii;
typedef vector VI;
map mp;
const int N = 1e6+10 ,mod = 998244353;
ll  dp[N][2];
int has_fa[N];

int n,x,y;
vector g[N];

void dfs(int u,int fa){
	dp[u][0] = x;
	dp[u][1] = 1;

	for(auto x  : g[u]){
		if(x == fa) continue;
		dfs(x,fa);
		dp[u][0] =  dp[u][0]*(dp[x][0]+dp[x][1]*y%mod)%mod;
		dp[u][1] =  dp[u][1]*(dp[x][0]+dp[x][1]*(y-1)%mod)%mod;
	}
}
void solve(){
	cin>>n>>x>>y;
	for(int i = 1; i>a>>b;
		g[a].pb(b);
		has_fa[b] = 1;
	}

	int root = 1;
	while(has_fa[root]) root++;

	dfs(root,0);
	cout