Tree matching

#include <bits/stdc++.h>
#define UNVISITED -1
#define MOD 1000000007
#define _ ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0), cout.precision(15);
using namespace std;

typedef long long int64;
typedef pair<int, int> ii;

vector< ii > children;
vector< vector<int> > memo;

int64 solve(int root, int match){
    int left = children[root].first, right = children[root].second;
    if(memo[root][match] != -1) return memo[root][match];

    int64 ans = 0;
    if(left != 0 && right != 0){
        ans = solve(left, false) * solve(right, false);
        if(match == false){
            ans %= MOD;
            ans += solve(left, true) * solve(right, false);
            ans %= MOD;
            ans += solve(left, false) * solve(right, true);
        }
    } else if(left != 0){
        ans = solve(left, false);
        if(match == false)  ans %= MOD, ans += solve(left, true);
    } else if(right != 0){
        ans = solve(right, false);
        if(match == false)  ans %= MOD, ans += solve(right, true);
    } else
        return 1;

    ans %= MOD;
    return memo[root][match] = ans;
}

int main(){ _
    int n;  cin >> n;
    children.assign(n+1, ii(0, 0));
    memo.assign(n+1, vector<int> (2, -1));

    for(int i = 1; i <= n; ++i)
        cin >> children[i].first >> children[i].second;

    solve(1, false);
    cout << memo[1][0]<< endl;

    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