#include "factories.h"
#include <vector>
#include <iostream>
using namespace std;
const int N = 500005;
typedef long long ll;
int dp[N][20],depth[N],subtree[N],vis[N],parent[N];
ll dist[N],XX[N][20],PP[N][20];
int A[N],B[N];
vector<pair<int,int>> adj[N];
int logt[N];
int QUERY=0;
void dfs1(int v, int p, int dep, ll x) {
dp[v][0]=p;
depth[v]=dep;
dist[v]=x;
for(int i=1;i<=logt[dep];i++) dp[v][i]=dp[dp[v][i-1]][i-1];
int c;
for(auto e:adj[v]) {
c=e.first;
if(c==p) continue;
dfs1(c,v,dep+1,x+e.second);
}
}
int find_centroid(int v, int p, int x) {
int c;
for(auto e:adj[v]) {
c=e.first;
if(c==p || vis[c] || subtree[c]<=x) continue;
return find_centroid(c,v,x);
}
return v;
}
void dfs2(int v, int p) {
int c;
subtree[v]=1;
for(auto e:adj[v]) {
c=e.first;
if(c==p || vis[c] ) continue;
dfs2(c,v);
subtree[v]+=subtree[c];
}
}
int lca(int a, int b) {
if(depth[a]>depth[b]) swap(a,b);
for(int i=logt[depth[b]];i>=0;i--) {
if(depth[b]-(1<<i)>=depth[a]) b=dp[b][i];
}
if(a==b) return a;
for(int i=logt[depth[b]];i>=0;i--) {
if(dp[a][i]!=dp[b][i]) a=dp[a][i],b=dp[b][i];
}
return dp[a][0];
}
ll distance(int a, int b) {
return dist[a]+dist[b]-2*dist[lca(a,b)];
}
void process(int v, int p) {
dfs2(v,0);
int u=find_centroid(v,0,subtree[v]/2);
vis[u]=1;
parent[u]=p;
int p2=u;
int i=0;
PP[u][i]=p2;
while(p2!=-1) {
XX[u][i]=distance(p2,u);
p2=parent[p2];i++;
PP[u][i]=p2;
}
int c;
for(auto e:adj[u]) {
c=e.first;
if(vis[c]) continue;
process(c,u);
}
}
void Init(int n, int A[], int B[], int D[]) {
for(int i=0;i<=n-2;i++) {
adj[A[i]+1].push_back({B[i]+1,D[i]});
adj[B[i]+1].push_back({A[i]+1,D[i]});
}
logt[0]=-1;
for(int i=1;i<=n;i++) {
logt[i]=logt[i-1];
if((i&-i)==i) logt[i]++;
}
dfs1(1,0,0,0);
process(1,-1);
}
long long Query(int S, int X[], int T, int Y[]) {
QUERY++;
int u,v;
for(int i=0;i<S;i++) {
u=X[i]+1;
for(int j=0;PP[u][j]!=-1;j++) {
v=PP[u][j];
if(A[v]!=QUERY) {
A[v]=QUERY;B[v]=XX[u][j];
}
else if(B[v]>XX[u][j]) {
B[v]=XX[u][j];
}
}
}
ll ans=1e17;
for(int i=0;i<T;i++) {
u=Y[i]+1;
for(int j=0;PP[u][j]!=-1;j++) {
v=PP[u][j];
if(A[v]==QUERY) {
// A[v]=QUERY;B[v]=X[u][j];
ans=min(XX[u][j]+B[v],ans);
}
}
}
return ans;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
6 ms |
248900 KB |
Output is correct |
2 |
Correct |
386 ms |
249164 KB |
Output is correct |
3 |
Incorrect |
406 ms |
249164 KB |
Output isn't correct |
4 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
3 ms |
248900 KB |
Output is correct |
2 |
Correct |
2273 ms |
267644 KB |
Output is correct |
3 |
Incorrect |
3929 ms |
270628 KB |
Output isn't correct |
4 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2479 ms |
267644 KB |
Output is correct |
2 |
Correct |
2549 ms |
267644 KB |
Output is correct |
3 |
Incorrect |
4273 ms |
269648 KB |
Output isn't correct |
4 |
Halted |
0 ms |
0 KB |
- |