#include <bits/extc++.h>
#include "factories.h"
#define all(v) v.begin(), v.end()
#define zip(v) sort(all(v)), v.erase(unique(all(v)), v.end())
using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
typedef pair<ll, ll> pll;
typedef pair<int, int> pint;
typedef tree<ll, null_type, less<ll>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
int n, q;
int sz[500050], use[500050], cent_papa[500050], papa[500050][23], dep[500050], papa_dist[500050];
ll dp[500050];
vector<pint> adj[500050];
ll m[500050];
void dfs(int u, int p=0) {
papa[u][0]=p;
dep[u]=dep[p]+1;
for(auto& [v, w]: adj[u]) {
if(v==p) continue;
dp[v]=dp[u]+w;
dfs(v,u);
}
}
int lca(int u, int v) {
if(dep[u]<dep[v]) swap(u,v);
for(int i=22;i>=0;i--) if(dep[u]-dep[v]>=(1<<i)) u=papa[u][i];
if(u==v) return u;
for(int i=22;i>=0;i--) if(papa[u][i] ^ papa[v][i]) u=papa[u][i], v=papa[v][i];
return papa[u][0];
}
ll get_dist(int u, int v) { return dp[u]+dp[v]-2*dp[lca(u,v)]; }
int get_size(int u, int p=0) {
sz[u]=1;
for(auto& [v, w]:adj[u]) {
if(use[v] || p==v) continue;
sz[u]+=get_size(v,u);
}
return sz[u];
}
int get_cent(int u, int p, int cnt) {
for(auto& [v, w]:adj[u]) {
if(use[v] || v==p) continue;
if(sz[v]>cnt/2) return get_cent(v,u,cnt);
}
return u;
}
void dnc(int u, int p=0) {//p는 이전 cent
int cent=get_cent(u,p,get_size(u,p));
cent_papa[cent]=p;
use[cent]=1;
for(auto& [v, w]:adj[cent]) if(!use[v]) dnc(v,cent);
}
void update(int u) {
int now=u;
ll nd=0;
do {
m[now]=min(m[now],nd);
nd+=papa_dist[now];
now=cent_papa[now];
} while(now);
}
void downdate(int u) {
int now=u;
do {
m[now]=1e18;
now=cent_papa[now];
} while(now);
}
ll query(int u) {
int now=u;
ll ret=1e18;
do {
ret=min(ret, get_dist(u,now) + m[now]);
now=cent_papa[now];
} while(now);
return (ret<1e18) ? ret : -1;
}
void Init(int N, int A[], int B[], int D[]) {
n=N;
for(int i=0;i<n-1;i++) {
adj[A[i]+1].emplace_back(B[i]+1,D[i]);
adj[B[i]+1].emplace_back(A[i]+1,D[i]);
}
dfs(1), dnc(1);
fill(m+1,m+n+1,1e18);
for(int j=1;j<23;j++) for(int i=1;i<=n;i++) papa[i][j]=papa[papa[i][j-1]][j-1];
for(int i=1;i<=n;i++) if(cent_papa[i]) papa_dist[i]=get_dist(i,cent_papa[i]);
}
long long Query(int S, int X[], int T, int Y[]) {
ll ret=1e18;
for(int i=0;i<S;i++) update(X[i]+1);
for(int i=0;i<T;i++) ret=min(ret,query(Y[i]+1));
for(int i=0;i<S;i++) downdate(X[i]+1);
return ret;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
31 ms |
41300 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
7 ms |
41308 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
31 ms |
41300 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |