| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1176825 | Kaztaev_Alisher | 트리 (IOI24_tree) | C++20 | 0 ms | 0 KiB |
#include <bits/stdc++.h>
#define ios ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define file(s) if (fopen(s".in", "r")) freopen(s".in", "r", stdin), freopen(s".out", "w", stdout)
#define all(a) a.begin() , a.end()
#define F first
#define S second
using namespace std;
using ll = long long;
const ll N = 2e5+5 , inf = 2e9 + 7;
const ll INF = 1e18 , mod = 1e9+7;
ll n , w[N] , p[N] , sz[N] , c[N];
vector<int> g[N];
void init(vector<int> P, vector<int> W) {
n = (int)P.size();
for(int i = 1; i <= n; i++){
p[i] = P[i-1]+1;
w[i] = W[i-1];
}
for(int i = 2; i <= n; i++){
g[p[i]].push_back(i);
}
}
void dfs(ll v , ll L , ll R){
sz[v] = 0;
c[v] = 0;
for(int to : g[v]){
dfs(to,L,R);
sz[v] += sz[to];
}
if(g[v].size() == 0){
c[v] = sz[v] = L;
} else {
if(sz[v] > R){
c[v] = R-sz[v];
} else if(sz[v] < L){
c[v] = L-sz[v];
}
sz[v] += c[v];
}
}
long long query(int L, int R) {
dfs(1,L,R);
ll ans = 0;
for(int i = 1; i <= n; i++){
ans += abs(c[i])*w[i];
}
return ans;
}
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;
}