// incorrect/sol_vp_fixed_guess2.cpp
#include "deliveries.h"
#include <algorithm>
#include <vector>
#include <iostream>
#include <numeric>
#include <random>
#include <queue>
using namespace std;
struct graph{
vector<long long> dist;
vector<int> cnt;
long long weight_sum;
int C;
};
vector<vector<pair<int, long long>>> g;
vector<int> ord, dist, under;
vector<bool> vis;
vector<graph> gds;
void dfs0(int x, int d){
vis[x] = true;
dist[x] = d;
under[x] = 1;
for(auto [y, w] : g[x]){
if(!vis[y]){
dfs0(y, d + 1);
under[x] += under[y];
}
}
}
int get_c(int x, int p, int n){
for(auto [y, w] : g[x]){
if(y != p && under[y]*2 > n){
return get_c(y, x, n);
}
}
return x;
}
long long dfs(graph &gd, int x, long long d){
vis[x] = true;
gd.dist[x] = d;
long long res = gd.cnt[x];
for(auto [y, w] : g[x]){
if(!vis[y]){
long long tmp = dfs(gd, y, w + d);
gd.weight_sum += w * tmp;
res += tmp;
}
}
return res;
}
void update(graph &gd, int x, int c){
if(x == 0) ++c;
gd.weight_sum += (c - gd.cnt[x]) * gd.dist[x];
gd.cnt[x] = c;
}
void init(int N, std::vector<int> U, std::vector<int> V, std::vector<int> T, std::vector<int> W) {
g.resize(N);
under.resize(N);
dist.resize(N);
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]);
}
// near centroid
vis.assign(N, false);
dfs0(0, 0);
int c = get_c(0, -1, N);
vis.assign(N, false);
dfs0(c, 0);
// end
const int B = min(N, 5000000/N);
mt19937 gen(42);
ord.resize(N);
iota(ord.begin(), ord.end(), 0);
sort(ord.begin(), ord.end(), [](int a, int b) -> bool { return dist[a] < dist[b]; });
ord.resize(B);
gds.resize(B);
W[0]++;
for(int i = 0; i < B; i++){
vis.assign(N, false);
gds[i].C = ord[i];
gds[i].weight_sum = 0;
gds[i].dist.resize(N);
gds[i].cnt = W;
dfs(gds[i], ord[i], 0);
}
return;
}
long long max_time(int S, int X) {
long long res = 1e18;
for(int i = 0; i < (int)gds.size(); i++){
update(gds[i], S, X);
res = min(res, gds[i].weight_sum);
// cout << "i: " << i << ' ' << gds[i].weight_sum << endl;
}
return res * 2;
}
