Submission #2326118

---

Source Code Expand

#include <bits/stdc++.h>
#define il inline
#define RG register
#define ll long long
#define inf (1LL<<60)
#define N (200005)

using namespace std;

struct edge{ int nt,to,dis; }g[N<<1];
struct E{ int u,v; ll w; }e[N*30];

int head[N],vis[N],son[N],sz[N],fa[N],a[N],n,num,tot;
ll dis[N],ans;

vector<int> st;

il int gi(){
  RG int x=0,q=1; RG char ch=getchar();
  while ((ch<'0' || ch>'9') && ch!='-') ch=getchar();
  if (ch=='-') q=-1,ch=getchar();
  while (ch>='0' && ch<='9') x=x*10+ch-'0',ch=getchar();
  return q*x;
}

il void insert(RG int from,RG int to,RG int dis){
  g[++num]=(edge){head[from],to,dis},head[from]=num; return;
}

il void getrt(RG int x,RG int p,RG int &rt){
  sz[x]=1,son[x]=0;
  for (RG int i=head[x],v;i;i=g[i].nt){
    v=g[i].to; if (v==p || vis[v]) continue;
    getrt(v,x,rt),sz[x]+=sz[v];
    son[x]=max(son[x],sz[v]);
  }
  son[x]=max(son[x],son[0]-sz[x]);
  if (son[rt]>=son[x]) rt=x; return;
}

il void getdis(RG int x,RG int p){
  st.push_back(x),sz[x]=1;
  for (RG int i=head[x],v;i;i=g[i].nt){
    v=g[i].to; if (v==p || vis[v]) continue;
    dis[v]=dis[x]+g[i].dis,getdis(v,x),sz[x]+=sz[v];
  }
  return;
}

il void solve(RG int x,RG int S){
  RG int rt=0; son[0]=S,getrt(x,0,rt),vis[rt]=1;
  st.clear(),dis[rt]=0,getdis(rt,0); RG ll res=inf; RG int p=0;
  for (RG int v : st) if ((dis[v]+=a[v])<res) res=dis[v],p=v;
  for (RG int v : st) e[++tot]=(E){p,v,res+dis[v]};
  for (RG int i=head[rt];i;i=g[i].nt)
    if (!vis[g[i].to]) solve(g[i].to,sz[g[i].to]);
  return;
}

il int cmp(const E &a,const E &b){ return a.w<b.w; }

il int find(RG int x){ return fa[x]==x ? x : fa[x]=find(fa[x]); }

int main(){
  n=gi(); for (RG int i=1;i<=n;++i) a[i]=gi(),fa[i]=i;
  for (RG int i=1,u,v,w;i<n;++i)
    u=gi(),v=gi(),w=gi(),insert(u,v,w),insert(v,u,w);
  solve(1,n),sort(e+1,e+tot+1,cmp);
  for (RG int i=1,x,y,k;i<=tot;++i){
    x=find(e[i].u),y=find(e[i].v); if (x==y) continue;
    ans+=e[i].w,fa[x]=y,++k; if (k==n-1) break;
  }
  cout<<ans; return 0;
}

Submission Info

Judge Result