#include "deliveries.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN = 100005; // Adjusted for potential larger constraints
vector<pair<int, int>> adj[MAXN];
ll delivery_counts[MAXN];
ll subtree_deliveries[MAXN];
ll total_deliveries = 0;
int num_cities;
/**
* Standard DFS to calculate the total deliveries in each subtree.
* @param u: current node
* @param p: parent node to prevent cycles
*/
void compute_subtree_sums(int u, int p) {
subtree_deliveries[u] = delivery_counts[u];
for (auto& edge : adj[u]) {
int v = edge.first;
if (v != p) {
compute_subtree_sums(v, u);
subtree_deliveries[u] += subtree_deliveries[v];
}
}
}
/**
* DFS to calculate the maximum travel time.
* Logic: For every edge, we maximize the number of crossings.
*/
ll calculate_max_time(int u, int p) {
ll total_time = 0;
for (auto& edge : adj[u]) {
int v = edge.first;
int weight = edge.second;
if (v != p) {
// Recursive call for children
total_time += calculate_max_time(v, u);
// Logic: Max crossings for this edge is 2 * min(deliveries inside, deliveries outside)
ll inside = subtree_deliveries[v];
ll outside = total_deliveries - inside;
total_time += 2LL * weight * min(inside, outside);
// If a subtree contains more than half the deliveries,
// the truck is forced to make extra crossings to finish them.
if (inside * 2 > total_deliveries) {
total_time += 2LL * weight;
}
}
}
return total_time;
}
void init(int N, vector<int> U, vector<int> V, vector<int> W, vector<int> T) {
num_cities = N;
for (int i = 0; i < N; i++) {
delivery_counts[i] = T[i];
adj[i].clear();
}
for (int i = 0; i < N - 1; i++) {
adj[U[i]].push_back({V[i], W[i]});
adj[V[i]].push_back({U[i], W[i]});
}
}
ll max_time(int city_index, int new_delivery_count) {
// Update the delivery count for the specific city
delivery_counts[city_index] = new_delivery_count;
// Recalculate subtree sums (required for the O(N) subtask approach)
compute_subtree_sums(0, -1);
total_deliveries = subtree_deliveries[0];
// Compute the maximum possible time starting and ending at City 0
return calculate_max_time(0, -1);
}
