#include "factories.h"
#include<bits/stdc++.h>
using namespace std;
struct edg{
int v;
long long w;
};
vector<edg>g[500001];
long long dis[500001];
int dep[500001];
int st[500001][19];
int sub[500001];
int use[500001];
void dfs(int u,int par){
for (auto v:g[u]){
if (v.v==par)continue;
dis[v.v]=v.w+dis[u];
dep[v.v]=dep[u]+1;
st[v.v][0]=u;
dfs(v.v,u);
}
}
int lca(int u,int v){
if (dep[u]<dep[v])swap(u,v);
int k=dep[u]-dep[v];
for (int i=18;i>=0;i--){
if (k>>i&1){
u=st[u][i];
}
}
if (u==v)return u;
for (int i=18;i>=0;i--){
if (st[u][i]==0||st[v][i]==0)continue;
if (st[u][i]!=st[v][i]){
u=st[u][i];
v=st[v][i];
}
}
return st[u][0];
}
long long cal(int u,int v){
return dis[u]+dis[v]-2*dis[lca(u,v)];
}
int dfs2(int u,int par){
sub[u]=1;
for (auto v:g[u]){
int lm=v.v;
if (use[lm]||lm==par)continue;
dfs2(lm,u);
sub[u]+=sub[lm];
}
return sub[u];
}
int centroid(int u,int p,int sz){
for (auto v:g[u]){
if (use[v.v]||v.v==p)continue;
if (sub[v.v]*2>sz)return centroid(v.v,u,sz);
}
return u;
}
int par[500001];
long long mxx[500001];
int decompose(int u,int p){
int sz=dfs2(u,0);
int cen=centroid(u,0,sz);
use[cen]=1;
if (p!=0){
par[cen]=p;
}
for (auto v:g[cen]){
if (use[v.v])continue;
decompose(v.v,cen);
}
return cen;
}
void Init(int N,int A[],int B[],int D[]){
for (int i=0;i<N-1;i++){
g[A[i]+1].push_back({B[i]+1,D[i]});
g[B[i]+1].push_back({A[i]+1,D[i]});
}
dfs(1,0);
for (int i=1;i<=18;i++){
for (int j=1;j<=N;j++){
st[i][j]=st[st[i][j-1]][j-1];
}
}
for (int i=1;i<=N;i++){
mxx[i]=1e17;
}
decompose(1,0);
}
void update(int u,int pos){
if (pos==0)return;
mxx[pos]=min(mxx[pos],cal(u,pos));
update(u,par[pos]);
}
void res(int u,int pos){
if (pos==0)return;
mxx[pos]=1e17;
res(u,par[pos]);
}
long long get(int u,int pos){
long long ans=1e17;
if (pos==0)return ans;
ans=min(ans,cal(u,pos)+mxx[pos]);
ans=min(ans,get(u,par[pos]));
return ans;
}
long long Query(int S,int X[],int T,int Y[]){
for (int i=0;i<T;i++){
Y[i]++;
update(Y[i],Y[i]);
}
long long ans=1e17;
for (int i=0;i<S;i++){
X[i]++;
ans=min(ans,get(X[i],X[i]));
}
for (int i=0;i<T;i++){
res(Y[i],Y[i]);
}
return ans;
}
/*int a[500001];
int b[500001];
long long d[500001];
int X[1000001];
int Y[1000001];
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
int n,q;
cin>>n>>q;
for (int i=1;i<n;i++){
cin>>a[i]>>b[i]>>d[i];
g[a[i]+1].push_back({b[i]+1,d[i]});
g[b[i]+1].push_back({a[i]+1,d[i]});
}
dfs(1,0);
for (int i=1;i<=18;i++){
for (int j=1;j<=n;j++){
st[i][j]=st[st[i][j-1]][j-1];
}
}
for (int i=1;i<=n;i++){
mxx[i]=1e17;
}
decompose(1,0);
for (int t=1;t<=q;t++){
int S,T;
cin>>S>>T;
for (int j=1;j<=S;j++)cin>>X[j];
for (int j=1;j<=T;j++)cin>>Y[j];
for (int i=1;i<=T;i++){
Y[i]++;
update(Y[i],Y[i]);
}
long long ans=1e17;
for (int i=1;i<=S;i++){
X[i]++;
ans=min(ans,get(X[i],X[i]));
}
for (int i=1;i<=T;i++){
res(Y[i],Y[i]);
}
cout<<ans<<'\n';
}
}*/
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
23 ms |
12372 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
8 ms |
12244 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
23 ms |
12372 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
