#include #include "factories.h"
#include <bits/stdc++.h>
#define nl "\n"
#define no "NO"
#define yes "YES"
#define fi first
#define se second
#define vec vector
#define task "main"
#define _mp make_pair
#define ii pair<int, int>
#define sz(x) (int)x.size()
#define all(x) x.begin(), x.end()
#define evoid(val) return void(std::cout << val)
#define FOR(i, a, b) for(int i = (a); i <= (b); ++i)
#define FOD(i, b, a) for(int i = (b); i >= (a); --i)
#define unq(x) sort(all(x)); x.resize(unique(all(x)) - x.begin())
using namespace std;
template<typename U, typename V> bool maxi(U &a, V b) {
if (a < b) { a = b; return 1; } return 0;
}
template<typename U, typename V> bool mini(U &a, V b) {
if (a > b) { a = b; return 1; } return 0;
}
const int N = (int)5e5 + 9;
const int mod = (int)1e9 + 7;
const long long INF = (long long)1e16;
template<typename T>
struct segment_tree {
int n; vector<T> t;
segment_tree () {};
segment_tree (int _n) {
n = _n; t.resize(n * 4 + 7);
FOR(i, 1, 4 * n) t[i] = INF;
}
void refine(int id) {
t[id] = min(t[id << 1], t[id << 1 | 1]);
}
void update(int id, int l, int r, int p, long long val) {
if (l == r) return void(t[id] = val);
int m = (l + r) >> 1;
if (p <= m) update(id << 1, l, m, p, val);
else update(id << 1 | 1, m + 1, r, p, val);
refine(id);
}
void update(int p, long long val) {
update(1, 1, n, p, val);
}
T get(int id, int l, int r, int u, int v) {
if (l > v || r < u) return INF;
if (l >= u && r <= v) return t[id];
int m = (l + r) / 2;
return min(get(id << 1, l, m, u, v), get(id << 1 | 1, m + 1, r, u, v));
}
T get(int l, int r) {
return get(1, 1, n, l, r);
}
};
const int LG = 19;
int h[N], par[N][LG + 1], see[N], tin[N], tout[N];
long long dist[N];
vector<ii> g[N];
int lca(int u, int v) {
if (u == v) return u;
if (h[u] < h[v]) swap(u, v);
FOD(j, LG, 0) if (h[par[u][j]] >= h[v]) u = par[u][j];
if (u == v) return u;
FOD(j, LG, 0) if (par[u][j] != par[v][j])
u = par[u][j], v = par[v][j];
return par[u][0];
}
segment_tree<long long> A, B;
long long Query(int x, int a[], int y, int b[]) {
FOR(i, 0, x - 1) ++a[i], see[a[i]] = 1;
FOR(j, 0, y - 1) ++b[j];
bool ok = 0; FOR(j, 0, y - 1) if (see[b[j]]) {
ok = 1; break ;
}
FOR(i, 0, x - 1) see[a[i]] = 0;
if (ok) {
return 0;
}
vector<int> p;
FOR(i, 0, x - 1) {
p.push_back(a[i]);
}
FOR(i, 0, y - 1) {
p.push_back(b[i]);
}
sort(p.begin(), p.end(), [&](int &x, int &y) {
return tin[x] < tin[y];
});
vec<int> lc;
FOR(i, 0, sz(p) - 2)
lc.push_back(lca(p[i], p[i + 1]));
unq(lc);
FOR(i, 0, x - 1) {
A.update(tin[a[i]], dist[a[i]]);
}
FOR(i, 0, y - 1) {
B.update(tin[b[i]], dist[b[i]]);
}
long long ans = INF;
for(int j : lc) {
long long k1 = A.get(tin[j], tout[j]);
if (k1 == INF) continue ; k1 -= dist[j];
long long k2 = B.get(tin[j], tout[j]);
if (k2 == INF) continue ; k2 -= dist[j];
ans = min(ans, k1 + k2);
}
FOR(i, 0, x - 1) {
A.update(tin[a[i]], INF);
}
FOR(i, 0, y - 1) {
B.update(tin[b[i]], INF);
}
return ans;
}
int _timer = 0;
void dfs(int u, int p) {
tin[u] = ++_timer;
FOR(j, 1, LG) par[u][j] = par[par[u][j-1]][j-1];
for(auto v : g[u]) if (v.fi ^ p) {
dist[v.fi] = dist[u] + v.se;
par[v.fi][0] = u;
h[v.fi] = h[u] + 1;
dfs(v.fi, u);
}
tout[u] = ++_timer;
}
void Init(int n, int x[], int y[], int w[]) {
FOR(i, 0, n - 2) {
++x[i], ++y[i];
g[x[i]].emplace_back(y[i], w[i]);
g[y[i]].emplace_back(x[i], w[i]);
}
A = segment_tree<long long> (2 * n);
B = segment_tree<long long> (2 * n);
dfs(1, 0); h[0] = -1;
}
/* Let the river flows naturally */
Compilation message
factories.cpp:1:10: error: #include expects "FILENAME" or <FILENAME>
1 | #include #include "factories.h"
| ^
factories.cpp: In function 'long long int Query(int, int*, int, int*)':
factories.cpp:119:9: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
119 | if (k1 == INF) continue ; k1 -= dist[j];
| ^~
factories.cpp:119:35: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
119 | if (k1 == INF) continue ; k1 -= dist[j];
| ^~
factories.cpp:121:9: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
121 | if (k2 == INF) continue ; k2 -= dist[j];
| ^~
factories.cpp:121:35: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
121 | if (k2 == INF) continue ; k2 -= dist[j];
| ^~
