Submission #2313303

---

Source Code Expand

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<iostream>
#define LL long long
#define inf 1e17
#define N 200005
#define forson(p) for(int i=head[p];i;i=ne[i])
using namespace std;
int gi()
{
    int res=0,s=1; char ch;
    for(ch=getchar();(ch<'0'||ch>'9')&&ch!='-';ch=getchar());
    if(ch=='-') s=-1,ch=getchar();
    for(;ch>='0'&&ch<='9';ch=getchar()) res=res*10+ch-48;
    return res*s;
}

int n,m,key[N],head[N],len[N<<1],to[N<<1],ne[N<<1],num,siz[N];
int mn,pos,F[N][20],dp[N],vis[N],col[N],que[N],fa[N],mark[N]; LL ans,dis[N][20];
struct tag
{
    int fr; LL mindis;
    void init() {fr=0,mindis=inf;}
    tag operator + (const LL &o) const {
	return (tag){fr,mindis+o};
    }
    bool operator < (const tag &o) const {
	return mindis==o.mindis ? fr<o.fr : mindis<o.mindis;
    }
}poi[N],now[N],tg;

void adde(int u,int v,int w) {
    to[++num]=v,ne[num]=head[u],head[u]=num,len[num]=w;
    to[++num]=u,ne[num]=head[v],head[v]=num,len[num]=w;
}
void findrt(int p,int f,int tot) {
    siz[p]=1; int mmax=0;
    forson(p) if(!vis[to[i]]&&to[i]!=f)
	findrt(to[i],p,tot),siz[p]+=siz[to[i]],mmax=max(mmax,siz[to[i]]);
    mmax=max(mmax,tot-siz[p]);
    if(mmax<mn) mn=mmax,pos=p;
}
void dfssiz(int p,int f) {
    siz[p]=1;
    forson(p) if(!vis[to[i]]&&to[i]!=f)
	dfssiz(to[i],p),siz[p]+=siz[to[i]];
}
void dfsdis(int p,int f,LL d,int o) {
    F[p][dp[p]-dp[o]]=o,dis[p][dp[p]-dp[o]]=d;
    forson(p) if(dp[to[i]]>dp[o] && to[i]!=f)
	dfsdis(to[i],p,d+len[i],o);
}
void solve(int p,int tot,int d) {
    mn=0x3f3f3f3f,pos=0; findrt(p,0,tot);
    p=pos,vis[p]=1,dp[p]=d;
    dfssiz(p,0);
    forson(p) if(!vis[to[i]])
	solve(to[i],siz[to[i]],d+1);
    dfsdis(p,0,0,p);
}
int cmp(int x,int y) {return col[x]<col[y];}
void upd(int x) {
    for(int k=0;k<dp[x];++k)
	if((tag){col[x],dis[x][k]+key[x]} < poi[ F[x][k] ])
	    poi[ F[x][k] ]=(tag){col[x],dis[x][k]+key[x]};
}
int findfa(int x) {return fa[x]==x?x:fa[x]=findfa(fa[x]);}
void askmn(int x) {
    tg.init();
    for(int k=0;k<dp[x];++k)
	if(poi[ F[x][k] ]+dis[x][k]<tg) tg=poi[ F[x][k] ]+dis[x][k];
    tg=tg+key[x];
}
int main()
{
    n=gi();
    for(int i=1;i<=n;++i) key[i]=gi();
    for(int i=1,u,v;i<n;++i)
	u=gi(),v=gi(),adde(u,v,gi());
    solve(1,n,1);
    for(int i=1;i<=n;++i) col[i]=i; m=n;
    //Boruvka
    while(m>1) {
	for(int i=1;i<=n;++i) que[i]=i;
	sort(que+1,que+n+1,cmp);
	for(int i=1;i<=n;++i) poi[i].init();
	for(int i=1,j=1;i<=n;) {
	    now[col[que[i]]].init();
	    for(j=i;col[que[j]]==col[que[i]] && j<=n;++j) {
		if(i==1) continue;
		askmn(que[j]);
		if(tg<now[col[que[i]]]) now[col[que[i]]]=tg;
	    }
	    for(;i<j;++i) upd(que[i]);
	}
	for(int i=1;i<=n;++i) poi[i].init();
	for(int i=n,j=n;i>=1;) {
	    for(j=i;col[que[j]]==col[que[i]] && j>=1;--j) {
		if(i==n) continue;
		askmn(que[j]);
		if(tg<now[col[que[i]]]) now[col[que[i]]]=tg;
	    }
	    for(;i>j;--i) upd(que[i]);
	}
	for(int i=1;i<=m;++i) fa[i]=i,mark[i]=0;
	for(int i=1;i<=m;++i)
	    if(findfa(now[i].fr)!=findfa(i))
		fa[fa[now[i].fr]]=fa[i],ans+=now[i].mindis;
	int mm=m; m=0;
	for(int i=1;i<=mm;++i)
	    if(!mark[findfa(i)]) mark[fa[i]]=++m;
	for(int i=1;i<=n;++i)
	    col[i]=mark[fa[col[i]]];
    }
    printf("%lld\n",ans);
    return 0;
}

Submission Info

Judge Result