#include "tree.h"
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define ll long long
const int N = 2e5 + 4;
int n;
vector<int> p, w;
vector<int> adj[N];
ll ans;
ll dfs(int v, ll l, ll r) {
if (adj[v].empty()) {
ans += l * w[v];
return l;
}
ll sum = 0;
for (int u : adj[v]) sum += dfs(u, l, r);
if (v==0 || w[p[v]] <= w[v]) {
ll t = max(0ll, sum - r);
ans += t * w[v];
sum -= t;
return sum;
}
else {
ll t = sum - l;
ans += t * w[v];
sum -= t;
return sum;
}
}
void init(std::vector<int> P, std::vector<int> W) {
n = P.size();
p = P;
w = W;
for (int i=1; i<n; i++) adj[p[i]].pb(i);
}
long long query(int L, int R) {
ans = 0;
dfs(0, L, R);
return ans;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |