// correct/solution-subtask2.cpp
#include "deliveries.h"
#include <iostream>
#include <vector>
#define MAXN 101000
using namespace std;
long long N, centroid, allSumW, ans;
vector<int> edge[MAXN];
long long W[MAXN];
long long sumW[MAXN];
long long T[MAXN];
bool dfs(int x){
sumW[x] = W[x];
bool flipped = false;
for(int i : edge[x]){
flipped |= dfs(i);
sumW[x] += sumW[i];
}
if(centroid==-1 && sumW[x] >= (allSumW + 1)/2){
centroid = x;
flipped = true;
}
if(flipped){
ans += (allSumW - sumW[x]) * T[x];
} else {
ans += sumW[x] * T[x];
}
return flipped;
}
void init(int NN, std::vector<int> UU, std::vector<int> VV, std::vector<int> TT, std::vector<int> WW){
N = NN;
vector<vector<pair<int,int>>> e(N);
for (int i=0; i+1<N; ++i) {
e[UU[i]].push_back({VV[i], TT[i]});
e[VV[i]].push_back({UU[i], TT[i]});
}
vector<int> AA(N, -1), q = {0};
vector<int> TTT(N, 0);
for (int i = 0; i < (int)q.size(); ++i) {
int u = q[i];
for (auto [v, t] : e[u]) {
if (AA[u] == v) continue;
AA[v] = u;
TTT[v] = t;
q.push_back(v);
}
}
for(int i=0; i<N-1; i++){
edge[AA[i+1]].push_back(i+1);
T[i+1] = TTT[i+1];
}
for(int i=0; i<N; i++){
W[i] = WW[i];
}
W[0]++;
for(int i=0; i<N; i++)
allSumW += W[i];
}
long long max_time(int S, int X){
if(S==0) X++;
allSumW -= W[S];
W[S] = X;
allSumW += W[S];
ans = 0; centroid = -1; dfs(0);
return 2*ans;
}
