#include "factories.h" #include <bits/stdc++.h> using namespace std; typedef pair<int,int> pii; typedef pair<long long ,long long> pll; typedef long long ll ; #define File freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout); #define all(V) V.begin(),V.end() #define setprec(x) fixed << setprecision(x) #define Mp(a,b) make_pair(a,b) #define len(V) (int)(V.size()) #define sep ' ' #define endl '\n' #define pb push_back #define fi first #define sec second #define popcount(x) __builtin_popcount(x) #define lid u<<1 #define rid (lid)|1 mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count()); const ll N = 1e6 + 10,SQ=320,LOG=21; const ll inf = 2e17 , MD = 1e9 + 7; inline ll md(ll x){ x %= MD; return (x < 0 ? x + MD : x);} vector<pii> g[N]; int st[N],ft[N],tim=1; int par[N][LOG]; int dis[N]; vector<pair<int,long long>> adj[N]; int col[N]; ll dp[N],dp1[N],dp2[N]; ll ps[N]; void dfs(int u,int p){ st[u] = tim++; par[u][0] = p; dis[u] = (u == p ? 0 : dis[p] + 1); for(int j =1 ;j < LOG;j++) par[u][j] = par[par[u][j-1]][j-1]; for(auto h : g[u]){ if(h.fi != p) { ps[h.fi] = ps[u] + h.sec; dfs(h.fi,u); } } ft[u] = tim; } int lift(int u,int k){ for(int j = 0 ;j < LOG;j++){ if(k&(1<<j)) u = par[u][j]; } return u; } int lca(int u,int v){ if(dis[u] > dis[v]) swap(u,v); v =lift(v,dis[v] - dis[u]); if(u==v) return u; for(int j = LOG-1;j >= 0;j--){ if(par[u][j] != par[v][j]){ u = par[u][j],v= par[v][j]; } } return par[u][0]; } void Init(int N,int A[],int B[],int D[]){ int n = N; for(int i = 0 ; i < n - 1;i++){ g[A[i]].pb({B[i],D[i]}); g[B[i]].pb({A[i],D[i]}); } fill(col,col+n+2,0); dfs(0,0); } void DFS(int u){ dp[u] = dp1[u] = dp2[u] = inf; for(auto h : adj[u]){ DFS(h.fi); dp1[u] = min(dp1[u],dp1[h.fi] + h.sec); dp2[u] = min(dp2[u],dp2[h.fi] + h.sec); dp[u] = min(dp[u],dp[h.fi]); } ll m1 = inf; for(auto h : adj[u]){ dp[u] = min(dp[u],dp1[h.fi] + h.sec + m1); m1 = min(m1,dp2[h.fi] + h.sec); } m1 = inf; for(auto h : adj[u]){ dp[u] = min(dp[u],dp2[h.fi] + h.sec + m1); m1 = min(m1,dp1[h.fi] + h.sec); } if(col[u] == 1) dp1[u] = 0; if(col[u] == 2) dp2[u] = 0; if(col[u] == 1) dp[u] = min(dp[u],dp2[u]); if(col[u] == 2) dp[u] = min(dp[u],dp1[u]); } long long Query(int S, int X[], int T, int Y[]){ vector<int> ver; for(int j = 0 ; j < S;j++) ver.pb(X[j]); for(int j = 0 ;j < S;j++) col[X[j]] = 1; for(int j = 0 ; j < T;j++) ver.pb(Y[j]); for(int j = 0 ; j < T;j++) col[Y[j]] = 2; sort(all(ver),[&](int u,int v){ return (st[u] < st[v]); }); int ln = len(ver); for(int j = 0 ; j + 1 < ln;j++) ver.pb(lca(ver[j],ver[j+1])); sort(all(ver),[&](int u,int v){ return st[u] < st[v]; }); ver.resize(unique(all(ver))-ver.begin()); function<bool(int,int)> is_anc = [&](int u,int v){ return (st[u] <= st[v] && ft[v] <= ft[u]); }; vector<int> stk; stk.pb(ver[0]); for(int j = 1;j < len(ver);j++){ while(!stk.empty() && !is_anc(stk.back(),ver[j])){ stk.pop_back(); } adj[stk.back()].pb({ver[j],ps[ver[j]] - ps[stk.back()]}); stk.pb(ver[j]); } DFS(ver[0]); for(auto h : ver) adj[h].clear(); for(int j = 0 ; j < S;j++) col[X[j]] = 0; for(int j = 0 ; j < T;j++) col[Y[j]] = 0; return dp[ver[0]]; }