// time_limit/sol_vp_brute_force_reroot.cpp
#include "deliveries.h"
#include <algorithm>
#include <vector>
#include <iostream>
using namespace std;
vector<vector<pair<int, long long>>> g;
vector<long long> weight, sz;
vector<int> up, height, cnt;
vector<bool> vis;
pair<int, int> dfs0(int x, int p, int d){
vis[x] = true;
up[x] = p;
pair<int, int> res = {d, x};
for(auto [y, w] : g[x]){
if(!vis[y]){
res = max(res, dfs0(y, x, d+1));
}
}
return res;
}
void dfs(int x, int p, int w_ = 0){
vis[x] = true;
weight[x] = w_;
up[x] = p;
sz[x] = cnt[x];
height[x] = 0;
for(auto [y, w] : g[x]){
if(!vis[y]){
dfs(y, x, w);
sz[x] += sz[y];
height[x] = max(height[x], height[y] + 1);
}
}
}
long long weight_sum = 0;
int C;
void update(int x, int c){
cnt[x] += c;
while(x != -1){
sz[x] += c;
weight_sum += weight[x] * c;
x = up[x];
}
}
int get_c(int x, long long m){
for(auto [y, w] : g[x]){
if(up[y] == x && sz[y]*2 > m){
weight_sum += (sz[x] - sz[y]*2) * weight[y];
long long tmp = sz[x];
sz[x] -= sz[y];
sz[y] = tmp;
up[x] = y;
up[y] = -1;
weight[x] = weight[y];
weight[y] = 0;
return get_c(y, m);
}
}
C = x;
return x;
}
void print(){
for(int i = 0; i < (int)g.size(); i++){
cout << "i: " << i << " sz: " << sz[i] << " w: " << weight[i] << " up: " << up[i] << " cnt: " << cnt[i] << endl;
}
}
void init(int N, std::vector<int> U, std::vector<int> V, std::vector<int> T, std::vector<int> W) {
g.resize(N);
sz.assign(N, 0);
up.assign(N, 0);
height.assign(N, 0);
weight.assign(N, 0);
cnt = W;
cnt[0]++;
for(int i = 0; i < N-1; i++){
g[U[i]].emplace_back(V[i], T[i]);
g[V[i]].emplace_back(U[i], T[i]);
}
vis.assign(N, false);
int tmp = dfs0(0, -1, 0).second;
vis.assign(N, false);
auto [d, s] = dfs0(tmp, -1, 0);
for(int i = 0; i < d/2; i++) s = up[s];
vis.assign(N, false);
dfs(s, -1);
C = s;
for(int i = 0; i < N; i++){
weight_sum += sz[i] * weight[i];
}
// cout << "C: " << C << endl;
// cout << "weight sum: " << weight_sum << endl;
return;
}
long long max_time(int S, int X) {
if(S == 0) X++;
update(S, X - cnt[S]);
get_c(C, sz[C]);
// cout << "centroid: " << c << endl;
// print();
return weight_sum * 2;
}
