#include <bits/stdc++.h>
#include "factories.h"
using namespace std;
#define all(x) (x).begin(), (x).end()
#define ll long long int
#define pii pair <int, int>
#define pb push_back
#define ff first
#define ss second
const int N = 5e5+5;
const ll inf = 1e18;
int rem[N], sub[N], par[N], sp[6*N][20];
ll w[N], lvl[N], cur[N];
vector<pii> E[N];
void dfs(int nd, int pr){
sub[nd] = 1;
for (auto i : E[nd]){
if (i.ff == pr or rem[i.ff]) continue;
dfs(i.ff, nd);
sub[nd] += sub[i.ff];
}
}
int centroid(int nd, int pr, int sz){
for (auto i : E[nd]){
if (i.ff == pr or rem[i.ff]) continue;
if (sub[i.ff]*2 > sz) return centroid(i.ff, nd, sz);
}
return nd;
}
void build(int nd, int pr){
int centr = centroid(nd, 0, sub[nd]);
rem[centr] = 1;
par[centr] = pr;
for (auto i : E[centr]){
if (!rem[i.ff]){
dfs(i.ff, 0);
build(i.ff, centr);
}
}
}
void dfs2(int nd, int pr){
for (auto i : E[nd]){
if (i.ff == pr) continue;
lvl[i.ff] = lvl[nd]+1;
w[i.ff] = w[nd]+i.ss;
sp[i.ff][0] = nd;
dfs2(i.ff, nd);
}
}
int LCA(int u, int v){
if (lvl[u] < lvl[v]) swap(u, v);
int diff = lvl[u]-lvl[v];
for (int i = 19; i >= 0; i--){
if (diff&(1<<i)) u = sp[u][i];
}
if (u == v) return v;
for (int i = 19; i >= 0; i--){
if (sp[u][i] != sp[v][i]){
u = sp[u][i];
v = sp[v][i];
}
}
return sp[u][0];
}
ll dist(int u, int v){
if (u == v) return 0ll;
return w[u]+w[v]-2*w[LCA(u,v)];
}
void Init(int n, int A[], int B[], int D[]){
for (int i = 0; i < n-1; i++){
A[i]++;
B[i]++;
E[A[i]].pb({B[i], D[i]});
E[B[i]].pb({A[i], D[i]});
}
dfs(1, 0);
build(1, 0);
dfs2(1, 0);
for (int i = 1; i <= 19; i++){
for (int j = 1; j <= n; j++) sp[i][j] = sp[sp[i][j-1]][j-1];
}
for (int i = 1; i <= n; i++) cur[i] = inf;
}
void remv(int nd){
while(nd){
cur[nd] = inf;
nd = par[nd];
}
}
void paint(int nd){
int u = nd;
while(u){
cur[u] = min(cur[u], dist(u, nd));
u = par[u];
}
}
ll find(int nd){
ll mn = inf;
int u = nd;
while(u){
mn = min(mn, dist(u, nd)+cur[u]);
u = par[u];
}
return mn;
}
long long Query(int S, int X[], int T, int Y[]){
for (int i = 0; i < S; i++){
X[i]++;
paint(X[i]);
}
ll ans = inf;
for (int i = 0; i < T; i++){
Y[i]++;
ans = min(ans, find(Y[i]));
}
for (int i = 0; i < S; i++) remv(X[i]);
return ans;
}
// int main ()
// {
// int n, q;
// cin >> n >> q;
// int A[n], B[n], D[n];
// for (int i = 0; i < n-1; i++){
// cin >> A[i] >> B[i] >> D[i];
// }
// Init(n, A, B, D);
// // cout << LCA(4, 7);
// for (int i = 0; i < q; i++){
// int S, T;
// cin >> S >> T;
// int X[S], Y[T];
// for (int j = 0; j < S; j++) cin >> X[j];
// for (int j = 0; j < T; j++) cin >> Y[j];
// cout << Query(S, X, T, Y) << '\n';
// }
// }
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
19 ms |
12372 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
7 ms |
12256 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
19 ms |
12372 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
