#include<bits/stdc++.h>
#include "factories.h"
using namespace std;
#define int long long
#define F first
#define S second
#define all(x) x.begin(),x.end()
#define pii pair<int,int>
#define pb push_back
#define sz(x) (int)(x.size())
#define chmin(x,y) x=min(x,y)
#define chmax(x,y) x=max(x,y)
#define vi vector<int>
#define vp vector<pii>
#define vvi vector<vi>
#define ykh mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count())
#define __lg(x) 63-__builtin_clzll(x)
#define pow2(x) (1LL<<x)
void __print(int x) {cerr << x;}
void __print(float x) {cerr << x;}
void __print(double x) {cerr << x;}
void __print(long double x) {cerr << x;}
void __print(char x) {cerr << '\'' << x << '\'';}
void __print(const char *x) {cerr << '\"' << x << '\"';}
void __print(const string &x) {cerr << '\"' << x << '\"';}
void __print(bool x) {cerr << (x ? "true" : "false");}
#ifdef local
void setio(){freopen("/Users/iantsai/Library/Mobile Documents/com~apple~CloudDocs/cpp/Empty.md","r",stdin);}
#define debug(x...) cerr << "[" << #x << "] = ["; _print(x)
#else
void setio(){}
#define debug(x...)
#endif
const int mxn=5e5+5;
vector<pii>adj[mxn];
int cnt[mxn];
bool vis[mxn];
vector<pair<int,long long>>p[mxn];
pair<long long,long long> mn[mxn];
void cnt_sz(int v,int pa){
cnt[v]=1;
for(auto [u,d]:adj[v]){
if(vis[u] or u==pa)continue;
cnt_sz(u,v);
cnt[v]+=cnt[u];
}
}
int find_cen(int v,int pa,int tar){
for(auto [u,d]:adj[v]){
if(vis[u] or u==pa)continue;
if(cnt[u]*2>tar)return find_cen(u,v,tar);
}
return v;
}
void dfs(int v,int pa,int top,int cur){
p[v].pb({top,cur});
for(auto [u,d]:adj[v]){
if(vis[u] or u==pa)continue;
dfs(u,v,top,cur+d);
}
}
void cen(int v){
cnt_sz(v,v);
v=find_cen(v,v,cnt[v]);
vis[v]=1;
dfs(v,v,v,0);
for(auto [u,d]:adj[v]){
if(vis[u])continue;
cen(u);
}
}
void Init(int N,int A[],int B[],int D[]){
for(int i=0;i<N-1;i++){
adj[A[i]].pb({B[i],D[i]});
adj[B[i]].pb({A[i],D[i]});
}
cen(1);
}
long long Query(int S,int X[],int T,int Y[]){
for(int i=0;i<S;i++){
for(auto [u,l]:p[X[i]]){
mn[u]={1e18,1e18};
}
}
for(int i=0;i<T;i++){
for(auto [u,l]:p[Y[i]]){
mn[u]={1e18,1e18};
}
}
long long ans=1e18;
for(int i=0;i<S;i++){
for(auto [u,l]:p[X[i]]){
chmin(mn[u].F,l);
}
}
for(int i=0;i<T;i++){
for(auto [u,l]:p[Y[i]]){
chmin(mn[u].S,l);
chmin(ans,mn[u].F+mn[u].S);
}
}
for(int i=0;i<S;i++){
for(auto [u,l]:p[X[i]]){
chmin(ans,mn[u].F+mn[u].S);
}
}
for(int i=0;i<T;i++){
for(auto [u,l]:p[Y[i]]){
chmin(ans,mn[u].F+mn[u].S);
}
}
return ans;
}
/*
input:
*/
Compilation message
factories.cpp: In function 'void cnt_sz(long long int, long long int)':
factories.cpp:42:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
42 | for(auto [u,d]:adj[v]){
| ^
factories.cpp: In function 'long long int find_cen(long long int, long long int, long long int)':
factories.cpp:49:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
49 | for(auto [u,d]:adj[v]){
| ^
factories.cpp: In function 'void dfs(long long int, long long int, long long int, long long int)':
factories.cpp:57:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
57 | for(auto [u,d]:adj[v]){
| ^
factories.cpp: In function 'void cen(long long int)':
factories.cpp:67:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
67 | for(auto [u,d]:adj[v]){
| ^
factories.cpp: In function 'long long int Query(long long int, long long int*, long long int, long long int*)':
factories.cpp:81:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
81 | for(auto [u,l]:p[X[i]]){
| ^
factories.cpp:86:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
86 | for(auto [u,l]:p[Y[i]]){
| ^
factories.cpp:92:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
92 | for(auto [u,l]:p[X[i]]){
| ^
factories.cpp:97:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
97 | for(auto [u,l]:p[Y[i]]){
| ^
factories.cpp:103:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
103 | for(auto [u,l]:p[X[i]]){
| ^
factories.cpp:108:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
108 | for(auto [u,l]:p[Y[i]]){
| ^
/usr/bin/ld: /tmp/ccc1Csif.o: in function `main':
grader.cpp:(.text.startup+0x37d): undefined reference to `Init(int, int*, int*, int*)'
/usr/bin/ld: grader.cpp:(.text.startup+0x412): undefined reference to `Query(int, int*, int, int*)'
collect2: error: ld returned 1 exit status
