32122023-02-22 16:41:17zsomborFájlrendszercpp17Elfogadva 40/4093ms14656 KiB
#include <iostream>
#include <vector>
using namespace std;
using ll = long long;

int n, a, b;
ll ans = 1, MOD = 1e9 + 7;
vector <vector <int>> g(1e5 + 1);
vector <int> db(1e5 + 1, 0);
vector <int> sum(1e5 + 1, 0);

void dfs(int x) {
    if (!g[x].size()) return;
    a = g[x][0]; b = g[x][1];
    if (db[x] > -1 && db[a] > -1) db[b] = db[x] - db[a];
    if (db[x] > -1 && db[b] > -1) db[a] = db[x] - db[b];
    dfs(g[x][0]); dfs(g[x][1]);
    a = g[x][0]; b = g[x][1];
    if (db[a] > -1 && db[b] > -1) db[x] = db[a] + db[b];
}

void solve(int x) {
    if (db[x] > -1) sum[x] = db[x];
    if (!g[x].size()) return;
    solve(g[x][0]); solve(g[x][1]);
    a = g[x][0]; b = g[x][1];
    if (db[x] == -1) {
        sum[x] = sum[a] + sum[b];
        return;
    }
    if (db[a] > -1) return;
    ans *= db[x] - sum[a] - sum[b] + 1;
    ans %= MOD;
    return;
}

int main()
{
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> a >> db[i];
        if (a) g[a].push_back(i);
    }
    for (int i = 1; i <= n; i++) if (g[i].size() == 1) g[i].push_back(0);
    dfs(1); dfs(1);
    solve(1);
    cout << ans;
}
RészfeladatÖsszpontTesztVerdiktIdőMemória
base40/40
1Elfogadva0/06ms8096 KiB
2Elfogadva0/046ms10548 KiB
3Elfogadva1/14ms8360 KiB
4Elfogadva1/14ms8616 KiB
5Elfogadva1/14ms9072 KiB
6Elfogadva1/14ms8928 KiB
7Elfogadva2/24ms9136 KiB
8Elfogadva2/27ms9192 KiB
9Elfogadva3/38ms9404 KiB
10Elfogadva3/38ms9720 KiB
11Elfogadva3/39ms10364 KiB
12Elfogadva3/312ms10544 KiB
13Elfogadva4/428ms11272 KiB
14Elfogadva4/439ms11832 KiB
15Elfogadva4/448ms12452 KiB
16Elfogadva4/493ms14656 KiB
17Elfogadva4/492ms14588 KiB