Tree matching

#include <iostream>
#include <string>
#include <vector>
#include <cstdint>

const unsigned long long N = 1000000007;

std::vector<long long> with;
std::vector<long long> without;
std::vector<std::pair<int, int>> children;

void figure_out(int i)
{
    int l = children[i].first;
    int r = children[i].second;

    if (l == -1) {
        if (r == -1) {
            with[i] = 1;
            without[i] = 1;
        }
        else {
            figure_out(r);
            with[i] = without[r];
            without[i] = (with[r] + without[r]) % N;
        }
    }
    else {
        figure_out(l);
        if (r == -1) {
            with[i] = without[l];
            without[i] = (with[l] + without[l]) % N;
        }
        else {
            figure_out(r);
            with[i] = (without[l] * without[r]) % N;
            without[i] = (with[i] + (with[l] * without[r]) + (with[r] * without[l])) % N;
        }
    }
}

int main()
{
    int n;
    std::cin >> n;

    with.resize(n, -1);
    without.resize(n, -1);

    for (int ni = 0; ni < n; ++ni) {
        int a, b;
        std::cin >> a >> b;
        children.emplace_back(a - 1, b - 1);
    }

    figure_out(0);

    // for (auto& w : with) std::cerr << w << " "; std::cerr << std::endl;
    // for (auto& w : without) std::cerr << w << " "; std::cerr << std::endl;

    std::cout << without[0] << std::endl;
}

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