#include "factories.h" //In the name of God #include<bits/stdc++.h> #pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math") /* _ _ _ _ | \ | | | | (_) | \| | ___ ___| | ___ | . ` |/ _ \/ _ \ |/ / | | |\ | __/ __/ <| | |_| \_|\___|\___|_|\_\_| */ using namespace std; typedef long long int lli; typedef long double ld; typedef pair<lli,lli> pii; typedef pair<pii,pii> piiii; typedef vector<lli> ve; typedef vector<pii> vp; const lli N=5e5+100; const lli mod=1e9+7;//998244353;//1e9+9 const lli INF=1e18; lli power(lli x,lli y){lli res = 1;x = x % mod;while(y>0){if( y & 1 ){res = (res * x) % mod;}y = y >> 1;x = (x * x)%mod;}return res;} lli modinv(lli x){return power(x,mod-2);} lli divide(lli x,lli y){return ((x%mod) * modinv(y))%mod;} #define all(v) v.begin(),v.end() #define MIN(v) *min_element(all(v)) #define MAX(v) *max_element(all(v)) #define migmig ios_base::sync_with_stdio(false),cout.tie(0), cin.tie(0); #define read freopen("input.txt", "r", stdin);freopen("output.txt", "w", stdout); #define minheap priority_queue<pair<lli,pii>, std::vector<pair<lli,pii>>, std::greater<pair<lli,pii>>> #define set_preci(x) cout << fixed << setprecision(x); // #define debug(x) cerr << (#x) << " " << (x) << endl #define MP make_pair #define PB push_back #define fi first #define se second #define SUM(v) accumulate(v.begin(),v.end(), 0LL) #define FOR(x,n) for(lli x = 0; x < n; x++) #define FORS(x,n) for(lli x = 1; x <= n; x++) #define TEST int TQPWIEJR; cin>>TQPWIEJR;while(TQPWIEJR--) #define BN(l,a) while(l){a.PB(l%2);l/=2;} #define lb lower_bound #define ub upper_bound #define endl "\n" #define sep " " #define SZ(X) (lli)X.size() lli tmp; int n; vector<pair<int,int>> adj[N]; bool mark[N]; bool vis[N]; int sz[N]; vector<int> ver; int mxs[N]; int Par[N]; lli dis[N]; ve dist[N]; lli f[N]; void dfs1(lli v){ ver.PB(v); vis[v] = 1; sz[v] = 1; for(auto [u,w] : adj[v]){ if(vis[u] == 1 || mark[u] == 1)continue; dfs1(u); sz[v] += sz[u]; mxs[v] = max(mxs[v],sz[u]); } } void dfs2(lli v){ vis[v] = 1; dist[v].PB(dis[v]); // if(v == 0){ // debug(dist[0].back()); // } for(auto [u,w] : adj[v]){ if(vis[u] == 1 || mark[u] == 1)continue; dis[u] = dis[v] + w; dfs2(u); } } void cent_decomp(lli yek,lli pedar = -1){ dfs1(yek); int m = SZ(ver); int cent = -1; for(int v : ver){ if(mxs[v] * 2 <= m && (m-sz[v])*2 <= m){ cent = v; } vis[v] = 0; } Par[cent] = pedar; dfs2(cent); for(auto u : ver){ dis[u] = 0; vis[u] = 0; sz[u] = 0,mxs[u] = 0; } mark[cent] = 1; vis[cent] = 1; ver.clear(); for(auto [v,w] : adj[cent]){ if(mark[v] == 0){ cent_decomp(v,cent); } } } void Init(int nud, int A[], int B[], int D[]) { n = nud; FOR(i,n-1){ lli a = A[i],b = B[i],c = D[i]; adj[a].PB(MP(b,c)); adj[b].PB(MP(a,c)); } FOR(i,n)f[i] = INF; cent_decomp(0,-1); } ve change; void add(lli v){ lli C = v; lli p = SZ(dist[v]) -1 ; while(C != -1){ f[C] = min(f[C],dist[v][p--]); change.PB(C); C = Par[C]; } } void rem(lli v){ lli C = v; lli p = SZ(dist[v]) -1 ; while(C != -1){ f[C] =INF; C = Par[C]; } } lli get(lli v){ lli res = INF; lli C = v; lli p = SZ(dist[v]) -1 ; while(C != -1){ res= min(res,dist[v][p--] + f[C]); C = Par[C]; } return res; } long long Query(int S, int X[], int T, int Y[]) { lli ans = INF; FOR(i,S){ add(X[i]); } FOR(i,T){ ans= min(ans,get(Y[i])); } for(auto i : change)f[i] = INF; change.clear(); return ans; }