#include "bits/stdc++.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];
vector<pair<int, long long>> 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];
}
long long 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(vtin[u], vtout[u], -val);
t.update(1, vtin[u] - 1, val);
t.update(vtout[u] + 1, timer, val);
}
void reroot(int u, int prev) {
if(red[u]) {
ans = min(ans, t.get());
// cout << t.get() << '\n';
}
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];
long long 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) {
red[u] = blue[u] = 0;
vth[u] = 0;
adj[u].clear();
}
return ans;
}
void Init(int _n, int a[], int b[], 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, int x[], int t, 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);
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
57 ms |
51800 KB |
Output is correct |
| 2 |
Correct |
2518 ms |
56964 KB |
Output is correct |
| 3 |
Correct |
2743 ms |
56400 KB |
Output is correct |
| 4 |
Incorrect |
2692 ms |
57212 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
11 ms |
51804 KB |
Output is correct |
| 2 |
Correct |
1662 ms |
141472 KB |
Output is correct |
| 3 |
Incorrect |
1837 ms |
146140 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
57 ms |
51800 KB |
Output is correct |
| 2 |
Correct |
2518 ms |
56964 KB |
Output is correct |
| 3 |
Correct |
2743 ms |
56400 KB |
Output is correct |
| 4 |
Incorrect |
2692 ms |
57212 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
