Idiot First Search

    1#include <bits/stdc++.h>
    2using namespace std;
    3using ll = long long;
    4const int inf = 1e9;
    5const long long INF = 1e17; //❄️
    6const int mod = 1e9 + 7;
    7void solve() {
    8    int n; cin >> n;
    9    vector<int> lft(n + 1), rit(n + 1), par(n + 1);
    10    for (int i = 1; i <= n; i++) {
    11        cin >> lft[i] >> rit[i];
    12        if (lft[i] != 0) par[lft[i]] = i;
    13        if (rit[i] != 0) par[rit[i]] = i;
    14    }
    15    par[1] = 0;
    16    vector<int> order;
    17    stack<int> stk;
    18    stk.push(1);
    19    while (!stk.empty()) {
    20        int v = stk.top(); stk.pop();
    21        order.push_back(v);
    22        if (lft[v] != 0) stk.push(lft[v]);
    23        if (rit[v] != 0) stk.push(rit[v]);
    24    }
    25    vector<ll> par_cost(n + 1);
    26    for (int i = order.size() - 1; i >= 0; i--) {
    27       if (lft[order[i]] == 0 && rit[order[i]] == 0) {
    28        par_cost[order[i]] = 1;
    29        } else {
    30        par_cost[order[i]] = (par_cost[lft[order[i]]] + par_cost[rit[order[i]]] + 3) % mod;
    31        }
    32    }
    33       vector<ll> root_cost(n + 1);
    34       root_cost[1] = par_cost[1];
    35       stk.push(1);
    36       while (!stk.empty()) {
    37        int v = stk.top(); stk.pop();
    38        if (lft[v] != 0) {
    39            root_cost[lft[v]] = (root_cost[v] + par_cost[lft[v]]) % mod;
    40            stk.push(lft[v]);
    41        }
    42        if (rit[v] != 0) {
    43            root_cost[rit[v]] = (root_cost[v] + par_cost[rit[v]]) % mod;
    44            stk.push(rit[v]);
    45        }
    46    }
    47    for (int i = 1; i <= n; i++) {
    48        cout << root_cost[i] << " \n"[i == n];
    49    }
    50}
    51int main() {
    52    ios::sync_with_stdio(0); cin.tie(0); 
    53    int t; cin >> t;
    54    while (t--) {
    55        solve();
    56    }
    57    return 0;
    58}