//#include "factories.h"
#include <bits/stdc++.h>
using namespace std;
const int M = 5e5 + 1;
int st[M], fn[M], t, cnt, n , loc[M], ql, qr , TV = 1, lg[2 * M];
vector<pair<int, long long>> adj[M];
long long dis[M], seg[2][M << 2];
pair<int, int> par[20][M << 1];
void dfs(int v, int p, long long d1, int h) {
dis[v] = d1;
st[v] = t++;
loc[v] = cnt;
par[0][cnt++] = {h, v};
for (auto u : adj[v])
if (u.first != p) {
dfs(u.first, v, d1 + 1ll * u.second, h + 1);
par[0][cnt++] = {h, v};
}
fn[v] = t - 1;
return;
}
void update(int i, long long k, bool g) {
i = i + TV;
// cout << "A" << i << " " << k << " " << g << endl;
seg[g][i] = k;
i /= 2;
while (i) {
// cout << i << " ";
seg[g][i] = min(seg[g][i << 1], seg[g][i << 1 | 1]);
// cout << seg[g][i] << endl;
i /= 2;
}
// cout << endl;
}
long long get(bool g) {
// cout << "B" << ql << " " << qr << " " << g << endl;
ql = ql + TV;
qr = qr + 1 + TV;
long long ret = 1e18;
while (ql < qr) {
// cout << ql << " " << qr << endl;
if (ql & 1)
ret = min(ret, seg[g][ql++]);
if (qr & 1)
ret = min(ret, seg[g][--qr]);
ql /= 2;
qr /= 2;
// cout << ret << endl;
}
// cout << endl;
return ret;
}
void rem(int i, bool g) {
// cout << "C" << i << " " << g << endl;
i = i + TV;
seg[g][i] = 1e18;
i /= 2;
while (i) {
// cout << i << " ";
seg[g][i] = 1e18;
// cout << seg[g][i] << endl;
i /= 2;
}
// cout << endl;
}
void Init(int N, int A[], int B[], int D[]) {
n = N;
for (int i = 0; i < n - 1; i++) {
adj[A[i]].push_back({B[i], D[i]});
adj[B[i]].push_back({A[i], D[i]});
}
dfs(0, 0, 0, 0);
// for (int i = 0; i < n; i++)
// cout << i << " " << st[i] << " " << fn[i] << endl;
for (int i = 2; i < 2 * n; i++)
lg[i] = lg[i / 2] + 1;
while (TV < N)
TV *= 2;
for (int i = 0; i < 2 * TV; i++)
seg[0][i] = seg[1][i] = 1e18;
for (int i = 1; i < 20; i++)
for (int j = 0; j + (1 << i) < 2 * n; j++)
par[i][j] = min(par[i - 1][j], par[i - 1][j + (1 << (i - 1))]);
}
long long Query(int S, int X[], int T, int Y[]) {
vector<pair<int, int>> sv;
for (int i = 0; i < S; i++) {
update(st[X[i]], dis[X[i]], 0);
sv.push_back({st[X[i]], X[i]});
}
for (int i = 0; i < T; i++) {
update(st[Y[i]], dis[Y[i]], 1);
sv.push_back({st[Y[i]], Y[i]});
}
sort(sv.begin(), sv.end());
long long ans = 1e18 ;
for (int i = 0; i < int(sv.size()); i++) {
int v = sv[i].second;
ql = st[v];
qr = fn[v];
long long f = get(0);
ql = st[v];
qr = fn[v];
f += get(1);
f -= (2ll * dis[v]);
ans = min(ans, f);
if (i < int(sv.size()) - 1) {
int vv = sv[i].second, uu = sv[i + 1].second;
if (loc[vv] > loc[uu])
swap(vv, uu);
int SV = loc[vv], SU = loc[uu], LG = lg[SU - SV + 1];
pair<int, int> lca = min(par[LG][SV], par[LG][SU - (1 << LG) + 1]);
v = lca.second;
ql = st[v];
qr = fn[v];
f = get(0);
ql = st[v];
qr = fn[v];
f += get(1);
f -= (2ll * dis[v]);
ans = min(ans, f);
}
}
for (int i = 0; i < S; i++)
rem(st[X[i]], 0);
for (int i = 0; i < T; i++)
rem(st[Y[i]], 1);
return ans;
}
signed main(){
ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0);
int V[6] = {0, 1, 2, 2, 4, 1}, U[6] = {1, 2, 3, 4, 5, 6}, DIS[6] = {4, 4, 5, 6, 5, 3};
Init(7, V, U, DIS);
int A[2] = {0, 6}, B[2] = {3, 4};
cout << Query(2, A, 2, B) << endl;
int AA[3] = {0, 1, 3}, BB[2] = {4, 6};
cout << Query(3, AA, 2, BB) << endl;
int AAA[1] = {2}, BBB[1] = {5};
cout << Query(1, AAA, 1, BBB);
return 0;
}
Compilation message
/usr/bin/ld: /tmp/ccbRdAJy.o: in function `main':
grader.cpp:(.text.startup+0x0): multiple definition of `main'; /tmp/ccR1mRJz.o:factories.cpp:(.text.startup+0x0): first defined here
collect2: error: ld returned 1 exit status
