Codeforces Round #522 (Div. 1) C. Vasya and Maximum Matching(dp)

タイトルリンク:http://codeforces.com/contest/1078/problem/C
 
dp[x][0]は、現在のノードがマッチングされておらず、後続でマッチング可能で、マッチングされていない可能性のあるスキーマ数を示す
dp[x][1]は、現在のノードがマッチングされておらず、後続でマッチングされなければならないシナリオ数を示す
dp[x][2]は、現在のノードが一致しているスキーマ数を表す
 
注意:
息子vが一致している場合、現在のノードは、0->1または2->2の状態からvにエッジを接続することができる.
 
コード:

#include
#define xx first
#define yy second
#define mp make_pair
#define pb push_back
using namespace std;
typedef long long ll;
typedef pair pii;
const int MAXN=3e5+5;
const int MOD=998244353;
vector E[MAXN];
int dp[MAXN][3];
int g[3];
void dfs(int now,int fa=0)
{
	dp[now][0]=1;
	for(int v:E[now])
	{
		if(v==fa) continue;
		dfs(v,now);
		g[0]=1LL*dp[now][0]*(dp[v][0]+dp[v][2])%MOD;
		g[1]=(1LL*dp[now][0]*dp[v][2]+1LL*dp[now][1]*(dp[v][0]+2LL*dp[v][2]))%MOD;
		g[2]=(1LL*(dp[now][0]+dp[now][1])*(dp[v][0]+dp[v][1])+dp[now][2]*(dp[v][0]+2LL*dp[v][2]))%MOD;
		memcpy(dp[now],g,sizeof(g));
	}
}
int main()
{
	//freopen("in.txt","r",stdin);
	//freopen("out.txt","w",stdout);
	int n;
	scanf("%d",&n);
	for(int i=1;i