#include "factories.h"
#include <bits/stdc++.h>
#define pb push_back
#define lld long long
#define Linf 1000000000000000000LL
using namespace std;
int N; lld ans;
int lev[500002];
pair<int,lld> par[500002][20];
int color[500002];
bool check[500002];
vector<pair<int,lld>> edge[500002];
void makepar(int x){
check[x] = true;
for(auto &i : edge[x]){
if(check[i.first]) continue;
lev[i.first] = lev[x]+1;
par[i.first][0].first = x; par[i.first][0].second = i.second;
for(int j=1; j<=19; j++){
par[i.first][j].first = par[par[i.first][j-1].first][j-1].first;
par[i.first][j].second = par[par[i.first][j-1].first][j-1].second+par[i.first][j-1].second;
}
makepar(i.first);
}
}
void Init(int n, int A[], int B[], int D[]) {
N = n;
for(int i=0; i<N-1; i++){
A[i]++; B[i]++;
edge[A[i]].pb({B[i],D[i]});
edge[B[i]].pb({A[i],D[i]});
}
makepar(1);
}
pair<lld,lld> dfs(int x){
check[x] = true;
pair<lld,lld> tmp = {Linf,Linf};
if(color[x] == 1) tmp.first = 0;
else if(color[x] == 2) tmp.second = 0;
for(auto &i : edge[x]){
if(check[i.first]) continue;
pair<lld,lld> t = dfs(i.first);
t.first += i.second; t.second += i.second;
ans = min(ans,tmp.first+t.second);
ans = min(ans,tmp.second+t.first);
tmp.first = min(tmp.first,t.first);
tmp.second= min(tmp.second,t.second);
}
return tmp;
}
int getpar(int x,int y){
if(lev[x] > lev[y]) swap(x,y);
for(int i=0; i<=19; i++){
if(((lev[y]-lev[x])&(1<<i)) == 0) continue;
y = par[y][i].first;
}
if(x == y) return x;
int t;
for(int i=0; i<=19; i++){
if(par[x][i].first == par[y][i].first){
t = i;
break;
}
}
while(t != 0){
t--;
if(par[x][t].first != par[y][t].first){
x = par[x][t].first;
y = par[y][t].first;
}
}
if(par[x][0].first == 0 && x == 1) exit(-1);
return par[x][0].first;
}
lld getdis(int x,int y){
if(lev[x] > lev[y]) swap(x,y);
lld tsum = 0;
for(int i=0; i<=19; i++){
if(((lev[y]-lev[x])&(1<<i)) == 0) continue;
tsum += par[y][i].second;
y = par[y][i].first;
}
return tsum;
}
lld Query(int S, int X[], int T, int Y[]) {
for(int i=0; i<S; i++) X[i]++;
for(int i=0; i<T; i++) Y[i]++;
if(S <= 10 && T <= 10){
ans = Linf;
for(int i=0; i<S; i++){
for(int j=0; j<T; j++){
int tmp = getpar(X[i],Y[j]);
ans = min(ans,getdis(X[i],tmp)+getdis(Y[j],tmp));
}
}
return ans;
}
for(int i=1; i<=N; i++){
color[i] = 0;
check[i] = false;
}
for(int i=0; i<S; i++) color[X[i]] = 1;
for(int i=0; i<T; i++) color[Y[i]] = 2;
ans = Linf;
dfs(1);
return ans;
}
Compilation message
factories.c:2:25: fatal error: bits/stdc++.h: No such file or directory
#include <bits/stdc++.h>
^
compilation terminated.
