#include<bits/stdc++.h> #include "factories.h" using namespace std; // define #define execute cerr << " Time: " << fixed << setprecision(6) << (1.0 * clock() / CLOCKS_PER_SEC) << "s\n"; #define ll long long #define ii pair <int , ll> #define iii pair <int , ii> #define se second #define fi first #define all(v) (v).begin() , (v).end() #define Unique(v) sort(all(v)) , v.resize(unique(all(v)) - v.begin()) #define bit(x,i) (((x) >> (i)) & 1LL) #define flip(x,i) ((x) ^ (1LL << (i))) #define ms(d,x) memset(d , x , sizeof(d)) #define exist __exist #define ends __ends #define visit visited #define left __left #define right __right #define prev __prev #define next __next #define sitingfake 1 #define orz 1 //constant const long long mod = 1e9 + 7; const long long linf = 4557430888798830399LL; const long long nlinf = -4485090715960753727LL; const int LOG = 20; const int inf = 1061109567; const int ninf = -1044266559; const int dx[] = {0 , -1 , 0 , 1}; const int dy[] = {-1 , 0 , 1 , 0}; template<typename T> bool maximize(T &a, const T &b) { if(a < b) {a = b; return 1;} return 0; } template<typename T> bool minimize(T &a, const T &b) { if(a > b) {a = b; return 1;} return 0; } void Plus(ll & a ,ll b) { b %= mod; a += b; if(a < 0) a += mod; a %= mod; return; } void Mul(ll & a, ll b) { (a *= (b % mod)) %= mod; return; } //code const int maxn = 5e5 + 7; vector <ii> adj[maxn]; int par[maxn]; ll pathLength[maxn] , Min[maxn]; bool isc[maxn]; int sz[maxn] , n; int in[maxn] , out[maxn] , depth[maxn] ,timer; int arr[maxn * 2][21]; void dfs(int u , int p) { in[u] = ++timer; arr[timer][0] = u; for(auto &[v , w]: adj[u]) { if(v != p) { depth[v] = depth[u] + 1; pathLength[v] = pathLength[u] + w; dfs(v , u); arr[++timer][0] = u; } } out[u] = timer; } void BuildLca() { for(int j = 1; (1 << j) <= timer ; j++) { for(int i = 1; i + (1 << j) - 1 <= timer ; i++) { arr[i][j] = (depth[arr[i][j - 1]] < depth[arr[i + (1 << (j - 1))][j - 1]]) ? arr[i][j - 1] : arr[i + (1 << (j - 1))][j - 1]; } } } int lca(int u , int v) { int l = in[u] , r = in[v]; if(l > r) swap(l , r); int k = __lg(r - l + 1); if(depth[arr[l][k]] < depth[arr[r - (1 << k) + 1][k]]) { return arr[l][k]; } return arr[r - (1 << k) + 1][k]; } ll dist(int u ,int v) { return pathLength[u] + pathLength[v] - 2 * pathLength[lca(u ,v)]; } void dfscount(int u , int p) { sz[u] = 1; for(auto &[v , w] : adj[u]) { if(v != p && !isc[v]) { dfscount(v , u); sz[u] += sz[v]; } } } int centroid(int u , int p , int Size) { for(auto &[v , w] : adj[u]) { if(v != p && !isc[v] && sz[v] > Size / 2) { return centroid(v , u , Size); } } return u; } void cd(int u , int p) { dfscount(u , -1); int c = centroid(u , -1 , sz[u]); isc[c] = 1; par[c] = p; for(auto &[v , w] : adj[c]) { if(!isc[v]) { cd(v , c); } } } void Add(int u) { int cur = u; while(cur != -1) { Min[cur] = min(Min[cur] , dist(u , cur)); cur = par[cur]; } } ll compute(int u) { ll ans = linf; int cur = u; while(cur != -1) { ans = min(ans , Min[cur] + dist(u , cur)); cur = par[cur]; } return ans; } void Reset(int u) { while(u != -1) { Min[u] = linf; u = par[u]; } } void Init(int N , int A[] , int B[] , int D[]) { n = N; for(int i = 0; i < n - 1; i++) { int u = A[i] , v = B[i] , d = D[i]; adj[u].push_back({v , d}); adj[v].push_back({u , d}); } dfs(0 , -1); BuildLca(); cd(0 , -1); ms(Min , 0x3f); } ll Query(int S , int X[] , int T , int Y[]) { for(int i = 0; i < S; i++) { Add(X[i]); } ll ans = linf; for(int i = 0; i < T; i++) { ans = min(ans , compute(Y[i])); } for(int i = 0; i < S; i++) { Reset(X[i]); } return ans; }