#include <bits/stdc++.h>
#include "factories.h"
using namespace std;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
typedef long long ll;
typedef unsigned long long ull;
typedef double db;
#define forinc(a, b, c) for(int a = b, _c = c; a <= _c; ++a)
#define fordec(a, b, c) for(int a = b, _c = c; a >= _c; --a)
#define rep(i, a) forinc(i, 1, a)
#define repv(i, a) forinc(i, 0, a - 1)
#define forv(a, b) for(auto &a : b)
#define ii pair<int, int>
#define fi first
#define se second
#define reset(f, x) memset(f, x, sizeof(f))
#define all(a) begin(a), end(a)
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define bit(x, i) (x >> (i - 1) & 1ll)
#define on(x, i) (x | (1ll << (i - 1)))
#define off(x, i) (x & ~(1ll << (i - 1)))
const int N = 5e5 + 5;
const long long INF = 1e18;
int n, que, dep[N], pd[N][32];
long long d[N], in[N], id, out[N], dd[N], s, t;
long long pf[N], sf[N], ans;
int st[N], top;
vector <ii> ad[N];
vector <ii> adj[N];
vector <int> del;
void dfs(int u, int par) {
in[u] = ++id;
forinc(i, 1, log2(n)) pd[u][i] = pd[pd[u][i - 1]][i - 1];
forv(v, ad[u]) if(v.fi != par) {
pd[v.fi][0] = u;
dep[v.fi] = dep[u] + 1;
d[v.fi] = d[u] + v.se;
dfs(v.fi, u);
}
out[u] = ++id;
}
int lca(int u, int v) {
if(dep[u] < dep[v]) swap(u, v);
int dif = dep[u] - dep[v];
fordec(i, log2(n), 0) if(dif >> i & 1) u = pd[u][i];
if(u == v) return u;
fordec(i, log2(n), 0) if(pd[u][i] != pd[v][i]) u = pd[u][i], v = pd[v][i];
return pd[u][0];
}
bool cmp(int x, int y) {
return in[x] < in[y];
}
int dist(int u, int v) {
int par = lca(u, v);
return d[u] + d[v] - 2 * d[par];
}
void dfs1(int u, int par) {
long long &x = pf[u], &y = sf[u];
x = dd[u]&1 ? 0 : INF, y = dd[u]&2 ? 0 : INF;
forv(v, adj[u]) {
if(v.fi != par) {
dfs1(v.fi, u);
x = min(x, pf[v.fi] + v.se);
y = min(y, sf[v.fi] + v.se);
}
}
ans = min(ans, x + y);
}
void Init(int n, int A[], int B[], int D[]) {
forinc(i, 0, n - 2) {
int u = A[i], v = B[i], c = D[i];
u++; v++;
ad[u].eb(v, c);
ad[v].eb(u, c);
}
dfs(1, -1);
}
long long Query(int s, int X[], int t, int Y[]) {
ans = INF;
//s = _s, t = _t;
vector <int> node;
forinc(i, 0, s - 1) {
int v = X[i];
v++, dd[v] = 1, node.pb(v);
}
forinc(i, 0, t - 1) {
int v = Y[i];
v++, dd[v] |= 2, node.pb(v);
}
sort(all(node), [](int x, int y){return ii(in[x],out[x])<ii(in[y],out[y]);});
forinc(i, 0, node.size() - 2) node.pb(lca(node[i], node[i + 1]));
sort(all(node)); node.erase(unique(all(node)), end(node));
sort(all(node), [](int x, int y){return ii(in[x],out[x])<ii(in[y],out[y]);});
top = 0;
forinc(i, 0, node.size() - 1) {
while(top && out[node[i]] >= out[node[st[top]]]) top--;
if(top) {
int u = node[i], v = node[st[top]];
adj[u].eb(v, dist(u, v));
adj[v].eb(u, dist(v, u));
}
st[++top] = i;
}
dfs1(node[0], -1);
forv(w, node) pf[w] = sf[w] = dd[w] = 0, adj[w].clear();
return ans;
}
/*
signed main() {
ios_base::sync_with_stdio(false);
if(fopen("inp.txt", "r")) {
freopen("inp.txt", "r", stdin);
//freopen("out.txt", "w", stdout);
}
int _n, que;
static int a[5000], b[5000], D[5000];
cin >> n >> que;
forinc(i, 0, n - 2) {
int u, v, c;
cin >> a[i] >> b[i] >> D[i];
}
Init(n, a, b, D);
dfs(1, -1);
while(que--) {
int _s, _t, v;
cin >> _s >> _t;
static int p[5005], q[5005];
forinc(i, 0, _s - 1) cin >> v, p[i] = v;
forinc(i, 0, _t - 1) cin >> v, q[i] = v;
cout << Query(_s, p, _t, q) << '\n';
}
}
*/
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
43 ms |
24320 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
22 ms |
24064 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
43 ms |
24320 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
