#include <bits/stdc++.h> #include "factories.h" //#define int long long #define debug cout << "ok\n"; #define SQR(x) (1LL * ((x) * (x))) #define MASK(i) (1LL << (i)) #define BIT(x, i) (((x) >> (i)) & 1) #define fi first #define se second #define pb push_back #define mp make_pair #define pii pair<int,int> #define pli pair<ll,int> #define vi vector<int> #define FAST ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0); typedef long long ll; typedef unsigned long long ull; typedef long double ld; typedef unsigned int ui; using namespace std; const int M = 1e9 + 7; const int INF = 1e9 + 7; const ll INFLL = (ll)2e18 + 7LL; const ld PI = acos(-1); const int dx[] = {1, -1, 0, 0, -1, 1, 1, -1}; const int dy[] = {0, 0, 1, -1, -1, -1, 1, 1}; template<class _, class __> bool minimize(_ &x, const __ y){ if(x > y){ x = y; return true; } else return false; } template<class _, class __> bool maximize(_ &x, const __ y){ if(x < y){ x = y; return true; } else return false; } template<class _,class __> void Add(_ &x, const __ y) { x += y; if (x >= M) { x -= M; } return; } template<class _,class __> void Diff(_ &x, const __ y) { x -= y; if (x < 0) { x += M; } return; } //-------------------------------------------------------------- const int MaxN = 5e5+7; const int Log = 20; const int can = 710; int h[MaxN],up[MaxN][Log],n; ll dist[MaxN],Dist[MaxN]; vector<pii> a[MaxN]; void dfs(int u,int p) { for (pii e : a[u]) { int v = e.fi; int w = e.se; if (v == p) continue; h[v] += h[u] + 1; dist[v] = dist[u] + w; up[v][0] = u; for (int i=1;i<Log;i++) up[v][i] = up[up[v][i-1]][i-1]; dfs(v,u); } } int LCA(int u,int v) { if (h[u] < h[v]) swap(u,v); for (int i=0;i<Log;i++) if (BIT(h[u]-h[v],i)) u = up[u][i]; if (u == v) return u; for (int i=Log-1;i>=0;i--) { if (up[u][i] != up[v][i]) { u = up[u][i]; v = up[v][i]; } } return up[u][0]; } int Dist_lca(int u,int v) { return dist[u] + dist[v] - 2 * dist[LCA(u,v)]; } void Init(int N, int A[], int B[], int D[]) { n = N; for (int i=1;i<N;i++) { int u = A[i-1]; int v = B[i-1]; int w = D[i-1]; a[u].pb(mp(v,w)); a[v].pb(mp(u,w)); } dfs(1,-1); } void Dijkstra(vi lis) { for (int i=1;i<=n;i++) Dist[i] = INFLL; priority_queue<pair<ll,int>,vector<pair<ll,int>>,greater<pair<ll,int>>> pq; for (int x : lis) { Dist[x] = 0; pq.push(mp(0,x)); } while (!pq.empty()) { int u = pq.top().se; ll du = pq.top().fi; pq.pop(); if (du != Dist[u]) continue; for (pii e : a[u]) { int v = e.fi; int w = e.se; if (minimize(Dist[v],du + w)) { pq.push(mp(Dist[v],v)); } } } } long long Query(int S, int X[], int T, int Y[]){ vi XX; for (int i=0;i<S;i++) XX.pb(X[i]); vi YY; for (int i=0;i<T;i++) YY.pb(Y[i]); if (S < T) { swap(S,T); swap(XX,YY); } if (S > can) { Dijkstra(XX); ll res = INFLL; for (int y : YY) minimize(res,Dist[y]); return res; } else { ll res = INFLL; for (int x : XX) { for (int y : YY) { minimize(res,Dist_lca(x,y)); } } return res; } } //void sol() { // int n,q; // vi U,V,W; // cin >> n >> q; // for (int i=1;i<n;i++) { // int u,v,w; // cin >> u >> v >> w; // U.pb(u); // V.pb(v); // W.pb(w); // } // Init(n,U,V,W); // for (int i=1;i<=q;i++) { // int S,T; // vi X,Y; // cin >> S >> T; // X.resize(S); // Y.resize(T); // for (int & x : X) cin >> x; // for (int & y : Y) cin >> y; // cout << Query(S,X,T,Y) << '\n'; // } //} // //signed main() { // freopen("test.inp","r",stdin); // freopen("test.out","w",stdout); // FAST // int t=1; // cin >> t; // while (t--) sol(); //}