#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 = 1e6+7; const int Log = 20; int sz[MaxN],Arr[MaxN],Tin[MaxN],Tout[MaxN],Left[MaxN][Log],Right[MaxN][Log],z[MaxN],cnt = 0,par[MaxN],h[MaxN]; ll dist[MaxN],f[MaxN]; bool isCT[MaxN]; vector<pii> a[MaxN]; void dfs(int u,int p) { sz[u] = 1; for (pii e : a[u]) { int v = e.fi; if (isCT[v] | v == p) continue; dfs(v,u); sz[u] += sz[v]; } } int GetCen(int u,int p,int r) { for (pii e : a[u]) { int v = e.fi; if (isCT[v] || v == p) continue; if (sz[v] * 2 >= sz[r]) return GetCen(v,u,r); } return u; } void Centroid(int u,int p) { dfs(u,-1); u = GetCen(u,-1,u); isCT[u] = true; if (p >= 0) par[u] = p; for (pii e : a[u]) { int v = e.fi; if (!isCT[v]) { Centroid(v,u); } } } void dfsss(int u,int p) { Arr[++cnt] = u; 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; dfsss(v,u); Arr[++cnt] = u; } } int LCA(int u,int v) { if (Tin[u] > Tin[v]) swap(u,v); if (Tin[u] <= Tin[v] && Tout[v] <= Tout[u]) return u; u = Tout[u]; v = Tin[v]; int tmp = z[v - u]; if (h[Right[u][tmp]] < h[Left[v][tmp]]) return Right[u][tmp]; else return Left[v][tmp]; } ll Dist(int u,int v) { // cout << u << ' ' << v << ' ' << LCA(u,v) << '\n'; return dist[u] + dist[v] - 2 * dist[LCA(u,v)]; } void Init(int N,int A[],int B[],int D[]) { for (int i=1;i<N;i++) A[i-1]++,B[i-1]++; 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)); } Centroid(1,-1); memset(f,0x3f,sizeof(f)); dfsss(1,-1); // for (int i=1;i<=N;i++) cout << dist[i] << ' '; cout << '\n'; for (int i=1;i<=cnt;i++) Tout[Arr[i]] = i; for (int i=cnt;i>=1;i--) Tin[Arr[i]] = i; z[1] = 0; for (int i=2;i<=cnt;i++) { z[i] = z[i-1]; while (MASK(z[i]+1) <= i) z[i]++; } for (int i=1;i<=cnt;i++) { Left[i][0] = Right[i][0] = Arr[i]; } for (int i=1;i<Log;i++) { for (int j=1;j<=cnt;j++) { if (j + MASK(i) - 1 <= cnt) { if (h[Right[j][i-1]] < h[Right[j+MASK(i-1)][i-1]]) Right[j][i] = Right[j][i-1]; else Right[j][i] = Right[j+MASK(i-1)][i-1]; } if (j - MASK(i) >= 0) { if (h[Left[j][i-1]] < h[Left[j-MASK(i-1)][i-1]]) Left[j][i] = Left[j][i-1]; else Left[j][i] = Left[j-MASK(i-1)][i-1]; } } } } void reset(int u) { while (u) { f[u] = INFLL; u = par[u]; } } void Upd(int u) { int v = u; while (v) { // cout << u << ' ' << v << ' ' << Dist(u,v) << '\n'; minimize(f[v],Dist(u,v)); v = par[v]; } } ll Get(int u) { ll res = INFLL; int v = u; while (v) { minimize(res,f[v] + Dist(v,u)); v = par[v]; } return res; } long long Query(int S,int X[],int T,int Y[]) { for (int i=0;i<S;i++) X[i]++; for (int i=0;i<T;i++) Y[i]++; for (int i=0;i<S;i++) Upd(X[i]); ll res = INFLL; for (int i=0;i<T;i++) minimize(res,Get(Y[i])); for (int i=0;i<S;i++) reset(X[i]); return res; } //int A_tmp[] = {0,1,2,2,4,1}; //int B_tmp[] = {1,2,3,4,5,6}; //int D_tmp[] = {4,4,5,6,5,3}; // //int X_tmp[] = {2}; //int Y_tmp[] = {5}; // //void sol() { // Init(7,A_tmp,B_tmp,D_tmp); // cout << Query(1,X_tmp,1,Y_tmp); //} // //signed main() { //// freopen("test.inp","r",stdin); //// freopen("test.out","w",stdout); // FAST // int t=1; //// cin >> t; // while (t--) sol(); //}