#include <bits/stdc++.h>
#include "deliveries.h"
using namespace std;
#define pb push_back
#define st first
#define nd second
typedef long long ll;
typedef long double ld;
const ll I = 1000LL * 1000LL * 1000LL * 1000LL * 1000LL * 1000LL;
const int II = 2 * 1000 * 1000 * 1000;
const ll M = 1000LL * 1000LL * 1000LL + 7LL;
const int N = 1000 * 1000 + 7;
int n;
ll tab[N], sum[N];
ll al = 0LL, answer;
vector<pair<int, ll>> ed[N];
bool vis[N];
void DFS(int v, ll ev)
{
vis[v] = true;
sum[v] = tab[v];
for(int i = 0; i < (int)ed[v].size(); ++i)
{
if(vis[ed[v][i].st]) continue;
DFS(ed[v][i].st, ed[v][i].nd);
sum[v] += sum[ed[v][i].st];
}
//cerr << answer << " dfs: " << v - 1 << " " << sum[v] << " " << al << " " << ev << "\n";
answer += (ll)min(sum[v], al - sum[v]) * 2LL * ev;
vis[v] = false;
}
void init(int _N, vector<int> U, vector<int> V, vector<int> T, vector<int> W)
{
n = _N;
for(int i = 1; i <= n; ++i) tab[i] = W[i - 1];
tab[1] += 1LL;
for(int i = 1; i <= n; ++i) al += tab[i];
for(int i = 0; i < n; ++i)
{
ed[U[i] + 1].pb(make_pair(V[i] + 1, (ll)T[i]));
ed[V[i] + 1].pb(make_pair(U[i] + 1, (ll)T[i]));
}
}
long long max_time(int S, int X)
{
answer = 0LL;
++S; if(S == 1) ++X;
al -= tab[S];
tab[S] = X;
al += tab[S];
//cerr << "nquery\n";
DFS(1, 0LL);
return answer;
}
