#include "deliveries.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN = 100005;
ll T_counts[MAXN];
ll edge_weights[MAXN]; // edge_weights[i] is the weight between city i and i+1
int num_cities;
struct SegmentTree {
ll tree_sum[MAXN << 2]; // Stores sum of T[i] in range
ll tree_weighted[MAXN << 2]; // Stores sum of (T[i] * distance_from_0) or similar
// Note: For a line, we actually want to track S_in for each edge.
// Let's use a simpler structure for the line.
} st;
// For Subtask 4 (Line), we can simplify the math:
// Total Time = Sum over all edges i: 2 * Weight_i * min(PrefixSum(i), Total - PrefixSum(i))
// There is a point 'K' where PrefixSum(K) > Total/2.
// Before K, min is PrefixSum. After K, min is (Total - PrefixSum).
struct LineSegmentTree {
ll t_sum[MAXN << 2]; // Sum of deliveries T[i]
ll weighted_dist[MAXN << 2]; // Sum of T[i] * distance_from_0
ll dist_from_0[MAXN];
void update(int node, int l, int r, int idx, int val) {
if (l == r) {
t_sum[node] = val;
weighted_dist[node] = (ll)val * dist_from_0[l];
return;
}
int mid = (l + r) >> 1;
if (idx <= mid) update(node << 1, l, mid, idx, val);
else update(node << 1 | 1, mid + 1, r, idx, val);
t_sum[node] = t_sum[node << 1] + t_sum[node << 1 | 1];
weighted_dist[node] = weighted_dist[node << 1] + weighted_dist[node << 1 | 1];
}
// Standard Segment Tree Walk to find the 'Weighted Median'
int find_centroid(int node, int l, int r, ll current_half) {
if (l == r) return l;
int mid = (l + r) >> 1;
if (t_sum[node << 1] >= current_half)
return find_centroid(node << 1, l, mid, current_half);
else
return find_centroid(node << 1 | 1, mid + 1, r, current_half - t_sum[node << 1]);
}
// Query sum of T[i] in range [ql, qr]
ll query_t(int node, int l, int r, int ql, int qr) {
if (ql > r || qr < l) return 0;
if (ql <= l && r <= qr) return t_sum[node];
int mid = (l + r) >> 1;
return query_t(node << 1, l, mid, ql, qr) + query_t(node << 1 | 1, mid + 1, r, ql, qr);
}
// Query sum of T[i]*dist in range [ql, qr]
ll query_w(int node, int l, int r, int ql, int qr) {
if (ql > r || qr < l) return 0;
if (ql <= l && r <= qr) return weighted_dist[node];
int mid = (l + r) >> 1;
return query_w(node << 1, l, mid, ql, qr) + query_w(node << 1 | 1, mid + 1, r, ql, qr);
}
} line_st;
void init(int N, vector<int> U, vector<int> V, vector<int> W, vector<int> T) {
num_cities = N;
// Assuming line is 0-1-2-...-(N-1) based on problem constraints for this subtask
// We calculate distance from city 0 to each city i
line_st.dist_from_0[0] = 0;
for (int i = 0; i < N - 1; i++) {
// Find which node is "further" in the line.
// In a line subtask, usually U[i]=i, V[i]=i+1.
int u = U[i], v = V[i], w = W[i];
line_st.dist_from_0[max(u, v)] = w;
}
for (int i = 1; i < N; i++) line_st.dist_from_0[i] += line_st.dist_from_0[i-1];
for (int i = 0; i < N; i++) {
T_counts[i] = T[i];
line_st.update(1, 0, N - 1, i, T[i]);
}
}
ll max_time(int s, int x) {
line_st.update(1, 0, num_cities - 1, s, x);
ll total_T = line_st.t_sum[1];
// 1. Find the city K that acts as the "weighted median"
int K = line_st.find_centroid(1, 0, num_cities - 1, (total_T + 1) / 2);
// 2. Mathematical derivation for the line:
// Distance = 2 * [ Sum_{i > K} (T_i * (dist_i - dist_K)) + Sum_{i < K} (T_i * (dist_K - dist_i)) ]
// This can be expanded into prefix sums and weighted sums:
ll dist_K = line_st.dist_from_0[K];
ll left_t = line_st.query_t(1, 0, num_cities - 1, 0, K - 1);
ll left_w = line_st.query_w(1, 0, num_cities - 1, 0, K - 1);
ll right_t = line_st.query_t(1, 0, num_cities - 1, K + 1, num_cities - 1);
ll right_w = line_st.query_w(1, 0, num_cities - 1, K + 1, num_cities - 1);
ll ans = 2 * ((left_t * dist_K - left_w) + (right_w - right_t * dist_K));
return ans;
}
