// time_limit/sol_vp_brute_force2.cpp
#include "deliveries.h"
#include <algorithm>
#include <vector>
#include <iostream>
#include <queue>
using namespace std;
struct node{
int x, upd;
long long w;
bool operator<(const node& n) const{
if(w != n.w) return w < n.w;
return x < n.x;
}
};
vector<vector<pair<int, long long>>> g;
vector<priority_queue<node>> g2;
vector<long long> weight, sz;
vector<int> up, height, cnt, upd;
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);
g2[x].push(node{y, 0, sz[y]});
}
}
}
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;
upd[x]++;
if(up[x] != -1){
g2[up[x]].push(node{x, upd[x], sz[x]});
}
x = up[x];
}
}
int get_c(int x, long long m){
while(!g2[x].empty() && g2[x].top().upd != upd[g2[x].top().x]) g2[x].pop();
return !g2[x].empty() && sz[g2[x].top().x]*2 > m ? get_c(g2[x].top().x, m) : 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);
g2.resize(N);
upd.assign(N, 0);
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]);
int c = get_c(C, sz[C]);
// cout << "centroid: " << c << endl;
// print();
long long res = weight_sum;
while(c != -1){
res += (sz[C] - sz[c] * 2) * weight[c];
c = up[c];
}
return res * 2;
}
