#include <bits/stdc++.h>
using namespace std;
#define f first
#define s second
#define pb push_back
#define ar array
#define all(x) x.begin(), x.end()
#define siz(x) (int)x.size()
#define FOR(x, y, z) for(int x = (y); x < (z); x++)
#define ROF(x, z, y) for(int x = (y-1); x >= (z); x--)
#define F0R(x, z) FOR(x, 0, z)
#define R0F(x, z) ROF(x, 0, z)
#define trav(x, y) for(auto&x:y)
using ll = long long;
using vi = vector<int>;
using vl = vector<long long>;
using pii = pair<int, int>;
using vpii = vector<pair<int, int>>;
template<class T> inline bool ckmin(T&a, T b) {return b < a ? a = b, 1 : 0;}
template<class T> inline bool ckmax(T&a, T b) {return b > a ? a = b, 1 : 0;}
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const char nl = '\n';
const int mxN = 5e5 + 10;
const int MOD = 1e9 + 7;
const long long infLL = 1e18;
struct centroid{
vector<vector<int>> adj;
vector<bool> vis;
vi par, sz;
int n;
void init(int _n){ n = _n; adj.resize(n); par.resize(n); sz.resize(n); vis.resize(n, 0);}
void add(int a, int b) {adj[a].pb(b); adj[b].pb(a);}
int find_size(int u, int p = -1) {
if(vis[u]) return 0;
sz[u] = 1;
trav(v, adj[u]){
if(v != p)
sz[u] += find_size(v, u);
}
return sz[u];
}
int find_centroid(int u, int p, int N){
trav(v, adj[u]){
if(v!=p&&!vis[v]&&sz[v]>N/2)
return find_centroid(v, u, N);
}
return u;
}
void init_centroid(int u = 0, int p = -1){
find_size(u);
int c = find_centroid(u, -1, sz[u]);
vis[c] = 1;
par[c] = p;
trav(v, adj[c])
if(!vis[v])
init_centroid(v, c);
}
}C;
struct LCA{
int n, m=0; vl d, depth; vector<ar<int, 25>> anc; vector<vector<pair<int, ll>>> adj;
void init(int _n){ n = _n; adj.resize(n); d.resize(n, 0LL); depth.resize(n, 0LL); anc.resize(n);}
void add(int a, int b, ll dist){ adj[a].pb({b, dist}); adj[b].pb({a, dist}); }
void dfs(int u = 0, int p = -1){
anc[u][0] = p; FOR(i, 1, 25) {anc[u][i]=(anc[u][i-1]==-1?-1:anc[anc[u][i-1]][i-1]);}
trav(v, adj[u]){
if(p == v.f) continue;
d[v.f] = d[u] + 1;
depth[v.f] = depth[u] + v.s;
dfs(v.f, u);
}
}
int lca(int a, int b){
if(d[a] < d[b]) swap(a, b);
int dif = d[a] - d[b];
R0F(i, 25){if(dif&(1<<i)) a = anc[a][i];}
if(a==b) return a;
R0F(i, 25){if(anc[a][i] == anc[b][i]) continue;a = anc[a][i]; b = anc[b][i];}
return anc[a][0];
}
ll dist(int a, int b){ int l = lca(a, b); return depth[a]+depth[b]-2*depth[l];}
} L;
int n, q; ll bst[mxN];
void upd(int u, int d){
int orig = u;
while(u != -1){
if(d==1)
ckmin(bst[u], L.dist(u, orig));
else
bst[u] = infLL;
u = C.par[u];
}
}
ll qry(int u){
int orig = u;
ll res = infLL;
while(u != -1){
ckmin(res, L.dist(u, orig) + bst[u]);
u = C.par[u];
}
return res;
}
void Init(int N, int A[], int B[], int* D){
n = N;
L.init(n);
C.init(n);
F0R(i, n){
bst[i] = infLL;
}
FOR(i, 1, n){
int e1 = A[i], e2 = B[i]; ll e3 = D[i];
L.add(e1, e2, e3);
C.add(e1, e2);
}
L.dfs();
C.init_centroid();
}
ll Query(int S, int x[], int T, int y[]){
F0R(i, S){
upd(x[i], 1);
}
ll ans = infLL;
F0R(i, T){
ckmin(ans, qry(y[i]));
}
F0R(i, S){
upd(x[i], 0);
}
return ans;
}
// int32_t main(){
// ios_base::sync_with_stdio(0); cin.tie(0);
// cin >> n >> q;
// C.init(n); L.init(n);
// FOR(i, 1, n){
// int e1, e2, e3;
// cin >> e1 >> e2 >> e3;
// L.add(e1, e2, e3);
// C.add(e1, e2);
// }
// F0R(i, n) bst[i] = infLL;
// L.dfs();
// C.init_centroid();
// F0R(Q, q){
// int S, T; cin >> S >> T;
// vi x(S), y(T);
// trav(X, x) cin >> X;
// trav(Y, y) cin >> Y;
// F0R(i, S){
// upd(x[i], 1);
// }
// ll ans = infLL;
// F0R(i, T){
// ckmin(ans, qry(y[i]));
// }
// cout << ans << nl;
// F0R(i, S){
// upd(x[i], 0);
// }
// }
// return 0;
// }
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
37 ms |
768 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
640 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
37 ms |
768 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
