| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1345694 | thesentro | 트리 (IOI24_tree) | C++20 | 0 ms | 0 KiB |
#include <cassert>
#include <cstdio>
#include <bits/stdc++.h>
using namespace std;
#define ll long long
int n;
std::vector<int> p, w;
ll maxi = 202020;
vector<vector<ll>>g(maxi);
vector<ll>val(maxi, 0);
ll res = 0;
void dfs(ll x, ll p, ll l, ll r)
{
ll sum = 0;
for (auto i:g[x])
{
if (i!=p)
{
dfs(i, x, l, r);
sum += val[i];
}
}
if (sum>r)
val[x] = r-sum;
if (sum<l)
val[x] = l-sum;
if (sum>=l and sum<=r)
val[x] = 0;
// cout<<x<<" "<<val[x]<<endl;
res += abs(val[x])*w[x];
}
void init(std::vector<int> P, std::vector<int> W) {
p = P;
w = W;
n = (int)p.size();
for (int i=1 ; i<n ; i++)
{
g[i].push_back(p[i]);
g[p[i]].push_back(i);
}
}
long long query(int L, int R) {
res = 0;
dfs(0, -1, L, R);
return res;
}
int main() {
int N;
assert(1 == scanf("%d", &N));
std::vector<int> P(N);
P[0] = -1;
for (int i = 1; i < N; i++)
assert(1 == scanf("%d", &P[i]));
std::vector<int> W(N);
for (int i = 0; i < N; i++)
assert(1 == scanf("%d", &W[i]));
int Q;
assert(1 == scanf("%d", &Q));
std::vector<int> L(Q), R(Q);
for (int j = 0; j < Q; j++)
assert(2 == scanf("%d%d", &L[j], &R[j]));
fclose(stdin);
init(P, W);
std::vector<long long> A(Q);
for (int j = 0; j < Q; j++)
A[j] = query(L[j], R[j]);
for (int j = 0; j < Q; j++)
printf("%lld\n", A[j]);
fclose(stdout);
return 0;
}