#include "factories.h"
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<ll,ll>
#define piii pair<ll,pii>
#define se second
#define fi first
#define maxn 500005
#define maxl 22
const ll inf=1e18;
vector<pii> edge[maxn];
pii ver[4*maxn];
piii pr[maxn];
ll n,q,sz,cnt,len,L[maxn],R[maxn],Min[2*maxn][maxl],cn[2*maxn],f[maxn],lg[2*maxn],dep[maxn],dt[maxn];
ll root[maxn];
bool cmp(pii a,pii b){
return L[a.first]<L[b.first];
}
void dfs(ll u,ll par){
L[u]=++cnt;len++;dt[u]=dt[par]+1;
f[u]=Min[len][0]=len;cn[len]=u;
for(pii v:edge[u]){
if(v.first==par) continue;
dep[v.first]=dep[u]+v.second;
dfs(v.first,u);
Min[++len][0]=f[u];
}
R[u]=cnt;
}
ll lca(ll u,ll v){
u=f[u];v=f[v];
if(u>v) swap(u,v);
ll p=lg[v-u+1],a=min(Min[u][p],Min[v-(1<<p)+1][p]);
return cn[a];
}
ll getdist(ll u,ll v){
return dep[u]+dep[v]-2*dep[lca(u,v)];
}
void build_sparse(){
for(ll i=2;i<=len;i++) lg[i]=lg[i/2]+1;
for(ll i=1;i<20;i++){
for(ll j=1;j<=(len-(1<<i)+1);j++) Min[j][i]=min(Min[j][i-1],Min[j+(1<<(i-1))][i-1]);
}
}
ll res=inf;
ll findroot(ll u){
if(u!=root[u]) return root[u]=findroot(root[u]);
return u;
}
void unions(ll u,ll v){
u=findroot(u);v=findroot(v);
ll a=lca(pr[u].fi,pr[v].fi),d=getdist(pr[u].fi,pr[v].fi);
res=min(res,min(pr[u].se.se+pr[v].se.fi,pr[u].se.fi+pr[v].se.se)+d);
root[v]=u;
pr[u].se.fi=min(inf,min(pr[u].se.fi+getdist(a,pr[u].fi),pr[v].se.fi+getdist(a,pr[v].fi)));
pr[u].se.se=min(inf,min(pr[u].se.se+getdist(a,pr[u].fi),pr[v].se.se+getdist(a,pr[v].fi)));
pr[u].fi=a;
}
pii cal(ll l,ll r){
if(l==r){
if(ver[l].second==1) return {0,inf};
else return {inf,0};
}
ll lt=l+1;
vector<piii> pp;
while(lt<=r){
ll nxt=upper_bound(ver+l,ver+r+1,make_pair(R[ver[lt].first],2LL))-ver-1;
pp.push_back({ver[lt].first,cal(lt,nxt)});lt=nxt+1;
}
vector<piii> x;
for(ll i=0;i<(ll)pp.size();i++){
root[pp[i].fi]=pp[i].fi;
pr[pp[i].fi]=pp[i];
}
for(ll i=0;i<(ll)pp.size()-1;i++) x.push_back({n-dt[lca(pp[i].fi,pp[i+1].fi)],{pp[i].fi,pp[i+1].fi}});
sort(x.begin(),x.end());
for(auto k:x){
unions(k.se.fi,k.se.se);
}
pii ans={inf,inf};
if(ver[l].second==1) ans.first=0;
else ans.second=0;
for(ll i=0;i<(ll)pp.size();i++){
if(ver[l].second==1) ans.second=min(ans.second,pp[i].se.se+dep[pp[i].fi]-dep[ver[l].fi]);
else ans.first=min(ans.first,pp[i].se.fi+dep[pp[i].fi]-dep[ver[l].fi]);
}
if(ver[l].second==1) res=min(res,ans.second);
else res=min(res,ans.first);
return ans;
}
long long Query(int s,int xs[],int t,int yt[]){
sz=s+t;
for(ll i=1;i<=s;i++){
ver[i].first=xs[i-1];ver[i].first++;
ver[i].second=1;
}
for(ll i=1;i<=t;i++){
ver[s+i].first=yt[i-1];ver[s+i].first++;
ver[s+i].second=2;
}
sort(ver+1,ver+sz+1,cmp);res=inf;
ll l=1;
vector<piii> pp;
while(l<=sz){
ll nxt=upper_bound(ver+1,ver+sz+1,make_pair(R[ver[l].first],2LL))-ver-1;
pp.push_back({ver[l].first,cal(l,nxt)});l=nxt+1;
}
vector<piii> x;
for(ll i=0;i<(ll)pp.size();i++){
root[pp[i].fi]=pp[i].fi;
pr[pp[i].fi]=pp[i];
}
for(ll i=0;i<(ll)pp.size()-1;i++) x.push_back({n-dt[lca(pp[i].fi,pp[i+1].fi)],{pp[i].fi,pp[i+1].fi}});
sort(x.begin(),x.end());
for(auto k:x) unions(k.se.fi,k.se.se);
return res;
}
void Init(int N, int A[],int B[],int D[]) {
n=N;
for(ll i=0;i<n-1;i++){
edge[A[i]+1].push_back({B[i]+1,D[i]});
edge[B[i]+1].push_back({A[i]+1,D[i]});
}
dfs(1,0);build_sparse();
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Runtime error |
627 ms |
524288 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Runtime error |
625 ms |
524288 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Runtime error |
627 ms |
524288 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
