#include "bits/stdc++.h"
#include "factories.h"
using namespace std;
const int maxn = 5e5 + 5;
const long long inf = 1e18;
const int lg = 20;
int n, q;
vector<pair<int, int>> g[maxn], adj[maxn];
int tin[maxn], tout[maxn], timer;
int h[maxn], up[maxn][lg + 1];
long long dep[maxn];
bool red[maxn];
bool blue[maxn];
long long ans;
int vtin[maxn], vtout[maxn];
long long vth[maxn];
long long mn[maxn];
struct segment_tree {
int n;
vector<long long> tree, lazy;
segment_tree() {}
segment_tree(int n) : n(n) {
tree.resize(n * 4 + 6, 0);
lazy.resize(n * 4 + 6, 0);
}
void down(int ind, int l, int r) {
tree[ind] += lazy[ind];
if(l != r) {
lazy[ind * 2] += lazy[ind];
lazy[ind * 2 + 1] += lazy[ind];
}
lazy[ind] = 0;
}
void update(int ind, int l, int r, int x, int y, long long val) {
if(lazy[ind]) down(ind, l, r);
if(l > y || r < x) return;
if(x <= l and r <= y) {
lazy[ind] = val;
down(ind, l, r);
return;
}
int mid = (l + r) / 2;
update(ind * 2, l, mid, x, y, val);
update(ind * 2 + 1, mid + 1, r, x, y, val);
tree[ind] = min(tree[ind * 2], tree[ind * 2 + 1]);
}
long long get(int ind, int l, int r, int x, int y) {
if(lazy[ind]) down(ind, l, r);
if(l > y || r < x) return inf;
if(x <= l and r <= y) return tree[ind];
int mid = (l + r) / 2;
return min(get(ind * 2, l, mid, x, y), get(ind * 2 + 1, mid + 1, r, x, y));
}
void update(int x, int y, long long val) {
if(x > y) return;
update(1, 1, n, x, y, val);
}
long long get(int x, int y) {
return get(1, 1, n, x, y);
}
long long get() {
return get(1, 1, n, 1, n);
}
} t;
void dfs(int u, int prev) {
tin[u] = ++timer;
for(auto e:g[u]) {
if(e.first == prev) continue;
h[e.first] = h[u] + 1;
dep[e.first] = dep[u] + e.second;
up[e.first][0] = u;
dfs(e.first, u);
}
tout[u] = timer;
}
bool is_anc(int u, int v) {
return tin[u] <= tin[v] and tout[v] <= tout[u];
}
int lca(int u, int v) {
if(h[u] < h[v]) swap(u, v);
int depth = h[u] - h[v];
for(int i = lg; i >= 0; --i) {
if(depth >> i & 1) u = up[u][i];
}
if(u == v) return u;
for(int i = lg; i >= 0; --i) {
if(up[u][i] != up[v][i]) {
u = up[u][i], v = up[v][i];
}
}
return up[u][0];
}
int dist(int u, int v) {
return dep[u] + dep[v] - 2 * dep[lca(u, v)];
}
void vt_dfs(int u, int prev) {
vtin[u] = ++timer;
if(blue[u]) t.update(vtin[u], vtin[u], vth[u]);
else t.update(vtin[u], vtin[u], inf);
for(auto e:adj[u]) {
int v = e.first, w = e.second;
if(v == prev) continue;
vth[v] = vth[u] + w;
vt_dfs(v, u);
}
vtout[u] = timer;
}
void update(int u, int val) {
t.update(tin[u], tout[u], -val);
t.update(1, tin[u] - 1, val);
t.update(tout[u] + 1, timer, val);
}
void reroot(int u, int prev) {
if(red[u]) {
ans = min(ans, t.get());
}
for(auto e:adj[u]) {
int v = e.first, w = e.second;
if(v == prev) continue;
update(v, w);
reroot(v, u);
update(v, -w);
}
}
long long virtual_tree(vector<int> &ver) {
for(auto &i:ver) ++i;
sort(ver.begin(), ver.end(), [](const int &x, const int &y) -> bool {
return tin[x] < tin[y];
});
ver.erase(unique(ver.begin(), ver.end()), ver.end());
int cur_sz = (int)ver.size();
for(int i = 1; i < cur_sz; ++i) {
ver.push_back(lca(ver[i], ver[i - 1]));
}
sort(ver.begin(), ver.end(), [](const int &x, const int &y) -> bool {
return tin[x] < tin[y];
});
ver.erase(unique(ver.begin(), ver.end()), ver.end());
stack<int> st;
st.push(ver[0]);
for(int i = 1; i < (int)ver.size(); ++i) {
while(!st.empty() and !is_anc(st.top(), ver[i])) st.pop();
if(!st.empty()) {
int u = st.top(), v = ver[i], w = dist(u, v);
adj[u].push_back({v, w});
adj[v].push_back({u, w});
}
st.push(ver[i]);
}
t = segment_tree((int)ver.size());
timer = 0;
vt_dfs(ver[0], 0);
ans = inf;
reroot(ver[0], 0);
// for(auto u:ver) cout << mn[u] << ' ';
// cout << '\n';
// for(auto u:ver) cout << u << " ";
// cout << '\n';
for(auto u:ver) {
red[u] = blue[u] = 0;
vth[u] = 0;
adj[u].clear();
}
return ans;
}
void Init(int _n, vector<int> a, vector<int> b, vector<int> d) {
n = _n;
for(int i = 0; i < n - 1; ++i) {
int u = a[i], v = b[i], w = d[i];
++u, ++v;
g[u].push_back({v, w});
g[v].push_back({u, w});
}
dfs(1, 0);
for(int i = 1; i <= lg; ++i) {
for(int u = 1; u <= n; ++u) {
up[u][i] = up[up[u][i - 1]][i - 1];
}
}
}
long long Query(int s, vector<int> x, int t, vector<int> y) {
vector<int> ver;
for(int i = 0; i < s; ++i) {
ver.push_back(x[i]);
red[x[i] + 1] = 1;
}
for(int i = 0; i < t; ++i) {
ver.push_back(y[i]);
blue[y[i] + 1] = 1;
}
return virtual_tree(ver);
}
Compilation message
/usr/bin/ld: /tmp/cc8m7M3d.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
