Tree matching

#include <iostream>
#include <vector>

using namespace std;
typedef long long ll;

const int N = 1000000;
const ll M = 1000000007;


int n;
int g[2][N+5];
ll dp[2][N+5];

void dfs(int s) {
	int cl = g[0][s];
	int cr = g[1][s];
	if (cl != 0) {
		dfs(cl);
	}
	if (cr != 0) {
		dfs(cr);
	}
	if (cl == 0 && cr == 0) {
		dp[0][s] = 1;
	}
	else if (cl == 0) {
		dp[0][s] = (dp[0][cr]+dp[1][cr])%M;
		dp[1][s] = dp[0][cr];
	}
	else if (cr == 0) {
		dp[0][s] = (dp[0][cl]+dp[1][cl])%M;
		dp[1][s] = dp[0][cl];
	}
	else {
		dp[0][s] = ((dp[0][cl]+dp[1][cl])*(dp[0][cr]+dp[1][cr]))%M;
		dp[1][s] = ((dp[0][cl] * (dp[0][cr]+dp[1][cr])) + ((dp[0][cl]+dp[1][cl]) * dp[0][cr]))%M;
	}
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cin >> n;
	for (int i = 1; i <= n; ++i) {
		cin >> g[0][i] >> g[1][i];
	}
	dfs(1);
	cout << ((dp[0][1] + dp[1][1])%M) << "\n";
	return 0;
}

Test 1

Verdict: ACCEPTED

Test 2

Verdict: ACCEPTED

Test 3

Verdict: ACCEPTED

Test 4

Verdict: ACCEPTED

Test 5

Verdict: ACCEPTED

Test 6

Verdict: ACCEPTED

Test 7

Verdict: ACCEPTED