#include "factories.h"
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
struct edg{
int v;
long long w;
};
vector<edg>g[500009];
vector<edg>lon[500009];
long long dis[500009];
int dep[500009];
int st[500009][21];
int sub[500009];
int use[500009];
int in[500009];
int ck[500009];
int cnt=0;
bool cmp(int i,int j){
return in[i]<in[j];
}
void dfs(int u,int par){
in[u]=++cnt;
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);
}
}
inline 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];
}
inline long long cal(int u,int v){
return dis[u]+dis[v]-2*dis[lca(u,v)];
}
long long cac[500009];//min 1
long long buoi[500009];//min 2
void Init(int n,int a[],int b[],int d[]){
for (int i=0;i<n-1;i++){
a[i]++;
b[i]++;
g[a[i]].push_back({b[i],d[i]});
g[b[i]].push_back({a[i],d[i]});
}
dfs(1,0);
for (int i=1;i<=18;i++){
for (int j=1;j<=n;j++){
cac[j]=buoi[j]=1e17;
st[j][i]=st[st[j][i-1]][i-1];
}
}
}
long long ans=1e17;
void redfs(int u){
if (use[u]==1)cac[u]=0;
if (use[u]==2)buoi[u]=0;
for (auto v:lon[u]){
redfs(v.v);
cac[u]=min(cac[u],cac[v.v]+v.w);
buoi[u]=min(buoi[u],buoi[v.v]+v.w);
}
ans=min(ans,cac[u]+buoi[u]);
}
long long Query(int s,int x[],int t,int y[]){
vector<int>tp;
for (int i=0;i<s;i++){
use[x[i]+1]=1;
ck[x[i]+1]=1;
tp.push_back(x[i]+1);
}
for (int i=0;i<t;i++){
use[y[i]+1]=2;
ck[y[i]+1]=1;
tp.push_back(y[i]+1);
}
sort(tp.begin(),tp.end(),cmp);
for (int i=1;i<(int)tp.size();i++){
int u=tp[i],v=tp[i-1];
if (ck[lca(u,v)]==0){
ck[lca(u,v)]=1;
tp.push_back(lca(u,v));
}
}
sort(tp.begin(),tp.end(),cmp);
vector<int>dit;
for (auto v:tp){
if (!dit.empty()){
dit.push_back(v);
}
else {
while (lca(dit.back(),v)!=dit.back())dit.pop_back();
lon[dit.back()].push_back({v,cal(dit.back(),v)});
dit.push_back(v);
}
}
ans=1e17;
redfs(dit[0]);
for (auto v:tp){
ck[v]=0;
lon[v].clear();
cac[v]=buoi[v]=1e17;
}
for (int i=0;i<s;i++){
use[x[i]+1]=0;
}
for (int i=0;i<t;i++){
use[y[i]+1]=0;
}
return ans;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
39 ms |
48716 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
38 ms |
48444 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
39 ms |
48716 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
