// correct/solution-subtask3.cpp
#include "deliveries.h"
#include <iostream>
#include <vector>
#define MAXN 101000
using namespace std;
long long N, centroid, allSumW, allSumTxW, flippedWT;
vector<int> edge[MAXN];
long long W[MAXN];
long long sumW[MAXN];
long long T[MAXN];
long long sumT[MAXN];
long long parent[MAXN];
void dfs(int x){
sumW[x] = W[x];
for(int i : edge[x]){
sumT[i] = sumT[x] + T[i];
dfs(i);
sumW[x] += sumW[i];
}
}
int findCentroid(int x){
for(int i:edge[x]){
if(sumW[i] >= (allSumW + 1) / 2){
flippedWT += T[i] * sumW[i];
return findCentroid(i);
}
}
return x;
}
void init(int NN, std::vector<int> /*UU*/, std::vector<int> /*VV*/, std::vector<int> TT, std::vector<int> WW){
N = NN;
parent[0] = -1;
for(int i=0; i<N-1; i++){
edge[i/2].push_back(i+1);
T[i+1] = TT[i];
parent[i+1] = i/2;
}
for(int i=0; i<N; i++){
W[i] = WW[i];
}
W[0]++;
dfs(0);
for(int i=0; i<N; i++){
allSumTxW += W[i] * sumT[i];
allSumW += W[i];
}
}
long long max_time(int S, int X){
if(S==0) X++;
long long diff = X - W[S];
allSumTxW += diff * sumT[S];
allSumW -= W[S];
W[S] = X;
allSumW += W[S];
while(S!=-1){
sumW[S] += diff;
S = parent[S];
}
flippedWT = 0;
int cent = findCentroid(0);
return 2 * (allSumTxW + allSumW * sumT[cent] - 2 * flippedWT);
}
