#include <bits/stdc++.h> #include "factories.h" using namespace std; const int mxN = 5e5 + 10; const long long inf = 5e18; vector<pair<int, int>> adj[mxN]; int st[mxN], en[mxN], tin = 0; long long sum[mxN], seg[mxN * 2]; void dfs(int u = 0, int par = 0){ st[u] = ++tin; for(auto [v, w] : adj[u]){ if(v ^ par){ sum[v] = (long long) sum[u] + w; dfs(v, u); } } en[u] = tin; } void update(int idx, long long val){ idx += tin; seg[idx] = val; while(idx > 1){ idx >>= 1; seg[idx] = min(seg[idx << 1], seg[idx << 1 | 1]); } } long long query(int l, int r){ l += tin, r += tin; long long ans = inf; while(l <= r){ if(l & 1) ans = min(ans, seg[l ++]); if(r & 1 ^ 1) ans = min(ans, seg[r --]); l >>= 1, r >>= 1; } return ans; } void Init(int N, int A[], int B[], int D[]) { for(int i = 0; i < N - 1; ++i){ adj[A[i]].push_back({B[i], D[i]}); adj[B[i]].push_back({A[i], D[i]}); } dfs(); for(int i = 0; i < 2 * mxN; ++i) seg[i] = inf; } long long get(vector<int> A, vector<int> B){ long long ans = inf; for(auto it : A) update(st[it], sum[it]); for(auto it : B) ans = min(ans, query(st[it], en[it]) - sum[it]); for(auto it : A) update(st[it], inf); return ans; } long long Query(int S, int X[], int T, int Y[]) { vector<int> a, b; for(int i = 0; i < S; ++i) a.push_back(X[i]); for(int i = 0; i < T; ++i) b.push_back(Y[i]); return min(get(a, b), get(b, a)); }