#include<iostream>
#include<vector>
#include<queue>
#include<stack>
#include<algorithm>
#include<limits.h>
#include<math.h>
#include<map>
#include<set>
#include<unordered_map>
#include<unordered_set>
#include<iomanip>
#include<cstring>
#include<random>
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
using namespace std;
int n,q;
vector<pair<int,int>>nodes[500000];
int par[500000][20];
int depth1[500000];
ll depth[500000];
void dfs1(int node,int p){
par[node][0]=p;
for(int i=1;i<20;i++)
par[node][i]=par[par[node][i-1]][i-1];
for(auto[ne,w]:nodes[node]){
if(ne==p)
continue;
depth[ne]=depth[node]+w;
depth1[ne]=depth1[node]+1;
dfs1(ne,node);
}
}
int get_parent(int node,int p){
for(int i=0;i<20;i++){
if(p&(1<<i)){
node=par[node][i];
}
}
return node;
}
int lca(int a,int b){
if(depth1[a]<depth1[b])
swap(a,b);
a=get_parent(a,depth1[a]-depth1[b]);
for(int i=19;i>=0;i--){
if(par[a][i]!=par[b][i]){
a=par[a][i];
b=par[b][i];
}
}
if(a!=b)
a=par[a][0];
return a;
}
ll dist(int a,int b){
int l=lca(a,b);
return depth[a]+depth[b]-2*depth[l];
}
void Init(int N,int A[],int B[],int D[]){
n=N;
for(int i=0;i<n-1;i++){
nodes[A[i]].emplace_back(B[i],D[i]);
nodes[B[i]].emplace_back(A[i],D[i]);
}
dfs1(0,0);
}
int cnode;
vector<pair<int,ll>>nodes2[500000];
int color[500000];
int new_node(){
nodes2[cnode].clear();
color[cnode]=0;
return cnode++;
}
ll res;
ll highest1[500000],highest2[500000];
void dfs2(int node,int p){
highest1[node]=1e18;
if(color[node]==1)
highest1[node]=0;
highest2[node]=1e18;
if(color[node]==2)
highest2[node]=0;
for(auto[ne,w]:nodes2[node]){
if(ne==p)
continue;
dfs2(ne,node);
highest1[node]=min(highest1[node],highest1[ne]+w);
highest2[node]=min(highest2[node],highest2[ne]+w);
}
if(color[node]==1)
res=min(res,highest2[node]);
if(color[node]==2)
res=min(res,highest1[node]);
if(color[node]==0)
res=min(res,highest1[node]+highest2[node]);
}
ll Query(int n1,int arr1[],int n2,int arr2[]) {
// construct compressed tree
cnode=0;
priority_queue<pair<int,pair<int,int>>>q; // (depth, (node, compressed_node))
for(int i=0;i<n1;i++){
int nn=new_node();
q.push({depth1[arr1[i]],{arr1[i],nn}});
color[nn]=1;
}
for(int i=0;i<n2;i++){
int nn=new_node();
q.push({depth1[arr2[i]],{arr2[i],nn}});
color[nn]=2;
}
while(q.size()>1){
auto r1=q.top();
int node1=r1.second.first;
int cnode1=r1.second.second;
q.pop();
auto r2=q.top();
int node2=r2.second.first;
int cnode2=r2.second.second;
q.pop();
int l=lca(node1,node2);
if(l==node2){
nodes2[cnode1].emplace_back(cnode2,depth[node1]-depth[node2]);
nodes2[cnode2].emplace_back(cnode1,depth[node1]-depth[node2]);
q.push({depth1[node1],{node1,cnode1}});
continue;
}
int cl=new_node();
q.push({depth1[l],{l,cl}});
nodes2[cnode1].emplace_back(cl,depth[node1]-depth[l]);
nodes2[cl].emplace_back(cnode1,depth[node1]-depth[l]);
nodes2[cnode2].emplace_back(cl,depth[node2]-depth[l]);
nodes2[cl].emplace_back(cnode2,depth[node2]-depth[l]);
}
int root=q.top().second.second;
res=1e18;
dfs2(root,root);
return res;
}
#ifdef JAKOB
void solve(){
int n,q;
cin>>n>>q;
vector<int>a(n-1),b(n-1),d(n-1);
for(int i=0;i<n-1;i++)
cin>>a[i]>>b[i]>>d[i];
Init(n,&a[0],&b[0],&d[0]);
while(q--){
int n1,n2;
cin>>n1>>n2;
vector<int>arr1(n1),arr2(n2);
for(int&i:arr1)
cin>>i;
for(int&i:arr2)
cin>>i;
cout<<Query(n1,&arr1[0],n2,&arr2[0])<<"\n";
}
}
int main(){
ios::sync_with_stdio(false);cout.tie(NULL);cin.tie(NULL);
//freopen("/Users/jakob/cp_testing/test.txt","r",stdin);freopen("output.out","w",stdout);
int t=1;//cin>>t;
while(t--)solve();
return 0;
}
#endif
/*
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
*/
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
27 ms |
50008 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
11 ms |
49752 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
27 ms |
50008 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
