#include "factories.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb(e) push_back(e)
#define mp(a,b) make_pair(a,b)
#define vf first
#define vs second
const int N = 500002,L=20;
int n;
vector<pair<int,int>> adj[N];
int tin[N],tout[N],timer,up[N][L];
ll dis[N][L];
int p[N];
bool vis[N];
int siz[N];
ll res[N];
void dfs(int node , int par , int di){
tin[node] = timer++;
up[node][0] = par;
dis[node][0] = di;
for(int i = 1; i < L; i++){
up[node][i] = up[up[node][i-1]][i-1];
dis[node][i] = dis[node][i-1] + dis[up[node][i-1]][i-1];
}
for(auto i : adj[node]){
if(i.vf != par){
dfs(i.vf , node , i.vs);
}
}
tout[node] = timer++;
}
bool is_lca(int x , int y){
return tin[x] <= tin[y] && tout[x] >= tout[y];
}
int find(int x , int y){
if(is_lca(x,y))return x;
if(is_lca(y,x))return y;
for(int i = L - 1; i >= 0; i--){
if(!is_lca(up[x][i] , y))x = up[x][i];
}
return up[x][0];
}
void size_init(int node , int par){
siz[node] = 1;
for(auto i : adj[node]){
if(i.vf != par && !vis[i.vf]){
size_init(i.vf,node);
siz[node] += siz[i.vf];
}
}
}
int find_centroid(int node , int par , int total){
for(auto i : adj[node]){
if(!vis[i.vf] && i.vf != par && siz[i.vf] >= total/2)return find_centroid(i.vf , node , total);
}
return node;
}
void centroid_decomposition(int node ,int par){
size_init(node , node);
node = find_centroid(node , node , siz[node]);
p[node] = par;
vis[node] = 1;
for(auto i : adj[node]){
if(!vis[i.vf]){
centroid_decomposition(i.vf , node);
}
}
}
void Init(int nn, int A[], int B[], int D[]) {
n = nn;
for(int i = 0; i < n-1; i++){
adj[A[i]].pb(mp(B[i],D[i]));
adj[B[i]].pb(mp(A[i],D[i]));
}
timer = 0;
dfs(0,0,0);
memset(vis,0,sizeof vis);
centroid_decomposition(0,-1);
memset(res,-1,sizeof res);
}
ll cal(int x , int y){
if(x == y)return 0;
ll ans = 0;
for(int i = L - 1; i >= 0; i--){
if(!is_lca(up[x][i] , y)){
ans += dis[x][i];
x = up[x][i];
}
}
ans += dis[x][0];
return ans;
}
long long Query(int a, int X[], int b, int Y[]) {
ll ans = 1e18;
for(int i = 0; i < a; i++){
int node = X[i];
res[node] = 0;
node = p[node];
while(node != -1){
int lca = find(X[i] , node);
ll distance = cal(X[i],lca);
if(res[node] == -1 || res[node] > distance)res[node] = distance;
node = p[node];
}
}
for(int i = 0; i < b; i++){
int node = Y[i];
while(node != -1){
if(res[node] != -1){
int lca = find(node , Y[i]);
ll distance = cal(lca , Y[i]);
ans = min(ans , res[node] + distance);
}
node = p[node];
}
}
for(int i = 0; i < a; i++){
int node = X[i];
while(node != -1){
if(res[node]==-1)break;
res[node] = -1;
node = p[node];
}
}
return ans;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
32 ms |
17020 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
11 ms |
16796 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
32 ms |
17020 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
