#include "factories.h"
#include <cstdio>
#include <algorithm>
#include <vector>
#define z exit(0)
#define F first
#define S second
#define mp make_pair
typedef long long ll;
using namespace std;
using pii = pair<int,int>;
const int N = 5e5 + 5, M = 1e6 + 5;
const ll inf = 1e18;
vector<pii> g[N]; vector<int> vt_g[N];
int col[N], tin[N], tout[N], LOG, m, euler[M], ST[M][21], T[M], V[N], st[N], vis[N];
ll dp[N];
void dfs(int u, int p){
euler[m++] = u;
for(pii it: g[u]){
int w = it.F, v = it.S;
if(v != p){ dp[v] = dp[u] + w; dfs(v, u); euler[m++] = u;}
}
}
int LCA(int u, int v){
int l = tin[u], r = tin[v];
if(l > r) swap(l, r);
int j = 31 - __builtin_clz(r-l+1);
return T[min(ST[l][j], ST[r-(1<<j)+1][j])];
}
ll d(int u, int v){ return dp[u] + dp[v] - (dp[LCA(u, v)]<<1LL);}
void Init(int n, int A[], int B[], int D[]){
for(int i = 0; i<n; ++i){ g[i].clear(); }
for(int i = 0, u, v, w; i<n-1; ++i){
u = A[i]; v = B[i]; w = D[i];
g[u].emplace_back(w, v); g[v].emplace_back(w, u);
}
dp[0] = m = 0; dfs(0, 0); LOG = 32 - __builtin_clz(m);
for(int i = m-1; i>=0; --i) tin[euler[i]] = tout[euler[i]] = i, T[i] = euler[i];
for(int i = 0; i<m; ++i) tout[euler[i]] = i, ST[i][0] = tin[euler[i]];
for(int j = 1; j<LOG; ++j){
for(int i = 0; i+(1<<j)-1<m; ++i){
ST[i][j] = min(ST[i][j-1], ST[i+(1<<(j-1))][j-1]);
}
}
}
bool anc(int u, int v){ return tin[u] <= tin[v] && tout[v] <= tout[u];}
int ded[N], sz[N], ct; ll ans, mn[3];
int fsz(int u){ sz[u] = 1; for(int v: vt_g[u]) if(!ded[v]) sz[u] += fsz(v); return sz[u];}
int fcen(int u, int tsz){ for(int v: vt_g[u]) if(!ded[v] && sz[v] > tsz/2) return fcen(v, tsz); return u;}
void efs(int u){
if(col[u] && col[ct] && col[u] != col[ct]) ans = min(ans, d(ct, u));
if(col[u] == 1 && mn[2] < inf) ans = min(ans, d(ct, u) + mn[2]);
if(col[u] == 2 && mn[1] < inf) ans = min(ans, d(ct, u) + mn[1]);
for(int v: vt_g[u]) if(!ded[v]) efs(v);
}
void ffs(int u){
mn[col[u]] = min(mn[col[u]], d(ct, u));
for(int v: vt_g[u]) if(!ded[v]) ffs(v);
}
void cd(int u){
ded[ct = u = fcen(u, fsz(u))] = true;
for(int v: vt_g[u]) if(!ded[v]) efs(v), ffs(v);
mn[0] = mn[1] = mn[2] = inf;
for(int v: vt_g[u]) if(!ded[v]) cd(v);
}
ll Query(int s, int X[], int t, int Y[]){
bool ch = false;
for(int i = m = 0; i<s; ++i){ col[X[i]] = 1; vis[X[i]] = 1; V[m++] = X[i];}
for(int i = 0; i<t; ++i){ col[Y[i]] = 2; V[m++] = Y[i]; if(vis[Y[i]]) ch = true;}
auto cmp = [&](int u, int v) { return tin[u] < tin[v];};
sort(V, V+m, cmp);
int mm = m;
for(int i = 1; i<m; ++i) V[mm++] = LCA(V[i-1], V[i]);
m = mm; sort(V, V+m, cmp); m = unique(V, V+m) - V;
//
int sz = 0;
st[sz++] = V[0];
for(int i = 1; i<m; ++i){
for(; sz > 1 && !anc(st[sz-1], V[i]); --sz) vt_g[st[sz-2]].push_back(st[sz-1]);
st[sz++] = V[i];
}
for(; sz > 1; --sz) vt_g[st[sz-2]].push_back(st[sz-1]);
ans = mn[0] = mn[1] = mn[2] = inf; cd(V[0]);
for(int i = 0; i<m; ++i) col[V[i]] = ded[V[i]] = vis[V[i]] = 0, vt_g[V[i]].clear();
if(ch) ans = 0;
return ans;
}
/*
signed main(){
int n, q; scanf("%d %d", &n, &q);
int A[n], B[n], D[n], X[n], Y[n];
for(int i = 0, u, v, w; i<n-1; ++i){
scanf("%d %d %d", &u, &v, &w);
A[i] = u; B[i] = v; D[i] = w;
}
Init(n, A, B, D);
for(int i = 0; i<q; ++i){
int s, t; scanf("%d %d", &s, &t);
for(int j = 0; j<s; ++j) scanf("%d", X+j);
for(int j = 0; j<t; ++j) scanf("%d", Y+j);
printf("%lld\n", Query(s, X, t, Y));
}
}
*/
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
26 ms |
24412 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
13 ms |
24156 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
26 ms |
24412 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
