| # | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 926971 | 2024-02-14T06:04:05 Z | Aiperiii | Factories (JOI14_factories) | C++14 | 0 ms | 0 KB |
#include <bits/stdc++.h>
#define int long long
#define ff first
#define ss second
#define all(x) x.begin(),x.end()
#define pb push_back
using namespace std;
const int N=5e5+5;
vector <pair <int,int> > g[N];
int jmp[N][20];
int d[N],dis[N],par[N];
void dfs(int v,int p){
for(auto to : g[v]){
if(to.ff!=p){
d[to.ff]=d[v]+1;
dis[to.ff]=dis[v]+to.ss;
par[to.ff]=v;
jmp[to.ff][0]=v;
dfs(to.ff,v);
}
}
}
int dist(int u,int v){
int ans=dis[u]+dis[v];
if(d[u]<d[v])swap(u,v);
int lca=0;
for(int i=19;i>=0;i--){
if(d[jmp[u][i]]>=d[v]){
u=jmp[u][i];
}
}
if(u==v)lca=u;
else{
for(int i=19;i>=0;i--){
if(d[jmp[u][i]]!=d[jmp[v][i]]){
u=jmp[u][i];
v=jmp[v][i];
}
}
lca=par[u];
}
return ans-dis[lca]*2;
}
signed main(){
ios_base::sync_with_stdio();
cin.tie(0);cout.tie(0);
int n,q;
cin>>n>>q;
for(int i=0;i<n-1;i++){
int u,v,w;
cin>>u>>v>>w;
g[u].pb({v,w});
g[v].pb({u,w});
}
dfs(0,0);
for(int i=1;i<20;i++){
for(int j=0;j<n;j++){
jmp[j][i]=jmp[jmp[j][i-1]][i-1];
}
}
while(q--){
int s,t;
cin>>s>>t;
vector <int> a(s),b(t);
for(int i=0;i<s;i++){
cin>>a[i];
}
for(int i=0;i<t;i++){
cin>>b[i];
}
int mn=1e9;
for(int i=0;i<s;i++){
for(int j=0;j<t;j++){
mn=min(mn,dist(a[i],b[j]));
}
}
cout<<mn<<"\n";
}
}
/*
7 3
0 1 4
1 2 4
2 3 5
2 4 6
4 5 5
1 6 3
2 2
0 6
3 4
3 2
0 1 3
4 6
1 1
2
5
*/