Submission #2313133

---

Source Code Expand

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
using namespace std;
typedef long long ll;
const int N=200010;
int tt,sum,rt,cnt,tp;
bool vis[N];
int head[N],to[N*2],nxt[N*2],s[N*2],sz[N],Mx[N],a[N],pa[N];
struct Dat {
    int x,y;ll z;
    inline bool operator < (const Dat &A) const {return z<A.z;}
} g[N],f[N*20],pre;
inline int gi() {
    int x=0,o=1;
    char ch=getchar();
    while(ch!='-'&&(ch<'0'||ch>'9')) ch=getchar();
    if(ch=='-') o=-1,ch=getchar();
    while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
    return x*o;
}
inline void get_rt(int x,int fa) {
    sz[x]=1,Mx[x]=0;
    for(int i=head[x];i;i=nxt[i]) {
	int y=to[i];
	if(!vis[y]&&y!=fa) {
	    get_rt(y,x),sz[x]+=sz[y];
	    Mx[x]=max(Mx[x],sz[y]);
	}
    }
    Mx[x]=max(Mx[x],sum-sz[x]);
    rt=(Mx[x]<Mx[rt]?x:rt);
}
inline void get_dep(int x,ll d,int fa) {
    g[++tp]=(Dat){x,0,d+a[x]};
    pre=min(pre,g[tp]);
    for(int i=head[x];i;i=nxt[i])
	if(!vis[to[i]]&&to[i]!=fa) get_dep(to[i],d+s[i],x);
}
inline void solve(int x) {
    vis[x]=1,tp=0,pre=(Dat){0,0,1LL<<60};
    get_dep(x,0,0);
    for(int i=1;i<=tp;i++)
	f[++cnt]=(Dat){pre.x,g[i].x,pre.z+g[i].z};
    for(int i=head[x];i;i=nxt[i]) {
	int y=to[i];
	if(!vis[y]) {
	    sum=sz[y],rt=0;
	    get_rt(y,x),solve(rt);
	}
    }
}
inline int find(int x) {return pa[x]==x?x:pa[x]=find(pa[x]);}
int main() {
    int n;
    cin>>n;
    for(int i=1;i<=n;i++) a[i]=gi(),pa[i]=i;
    for(int i=1;i<n;i++) {
	int x=gi(),y=gi(),z=gi();
	to[++tt]=y,nxt[tt]=head[x],s[tt]=z,head[x]=tt;
	to[++tt]=x,nxt[tt]=head[y],s[tt]=z,head[y]=tt;
    }
    Mx[0]=sum=n,get_rt(1,0);
    solve(rt);
    sort(f+1,f+1+cnt);
    ll ans=0;
    for(int i=1;i<=cnt;i++) {
	int x=find(f[i].x),y=find(f[i].y);
	if(x!=y) pa[x]=y,ans+=f[i].z;
    }
    cout<<ans;
    return 0;
}

Submission Info

Judge Result