Language: C++

#include <iostream>
#include <cmath>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <queue>
#include <cassert>
#include <vector>
using namespace std;
struct bian{
	int next,point,w;
}b[410000];
const int N=210000;
int p[N],len,x[N],father[N],whe[N],pd[N],n,pren,now,size[N],where;
void ade(int k1,int k2,int k3){
	b[++len]=(bian){p[k1],k2,k3}; p[k1]=len;
}
void add(int k1,int k2,int k3){
	ade(k1,k2,k3); ade(k2,k1,k3);
}
long long f[N];
long long ans;
struct atom{
	int u,v;
	long long w;
}A[N];
int findfather(int k1){
	if (father[k1]==k1) return k1; return father[k1]=findfather(father[k1]);
}
int dfs1(int k1,int k2){
	size[k1]=1;
	for (int i=p[k1];i;i=b[i].next){
		int j=b[i].point;
		if (j!=k2&&pd[j]==0) size[k1]+=dfs1(j,k1);
	}
	return size[k1];
}
void dfs2(int k1,int k2){
	int num=n-size[k1];
	for (int i=p[k1];i;i=b[i].next){
		int j=b[i].point;
		if (j!=k2&&pd[j]==0){
			num=max(num,size[j]); dfs2(j,k1);
		}
	}
	if (num<now){
		now=num; where=k1;
	}
}
struct atom2{
	long long f,g;
	int tagf,tagg;
	void update(long long k1,int t){
		if (t==tagf){
			f=min(f,k1); return;
		}
		if (k1<f){
			g=f; f=k1; tagg=tagf; tagf=t;
		} else if (k1<g){
			g=k1; tagg=t;
		}
	}
}cur;
vector<int>go,gow;
void getnew(int k1,long long k2,int k3){
	if (k2<f[k1]){
		f[k1]=k2; whe[k1]=k3;
	}
}
void update(int k1,long long k2){
	k2+=x[k1];
	if (father[k1]==cur.tagf) getnew(k1,cur.g+k2,cur.tagg);
	else getnew(k1,cur.f+k2,cur.tagf);
}
void dfs3(int k1,int k2,long long k3){
	update(k1,k3);
	for (int i=p[k1];i;i=b[i].next){
		int j=b[i].point;
		if (j!=k2&&pd[j]==0) dfs3(j,k1,k3+b[i].w);
	}
}
void dfs4(int k1,int k2,long long k3){
	cur.update(k3+x[k1],father[k1]);
	for (int i=p[k1];i;i=b[i].next){
		int j=b[i].point;
		if (j!=k2&&pd[j]==0) dfs4(j,k1,k3+b[i].w);
	}
}
void solve(int k1){
	n=dfs1(k1,0); now=n; dfs2(k1,0); int k=where; pd[k]=1;
	//cout<<"asd "<<k<<endl;
	cur=(atom2){x[k],1e18,father[k]}; go.clear(); gow.clear();
	for (int i=p[k];i;i=b[i].next){
		int j=b[i].point;
		if (pd[j]==0){
			dfs3(j,0,b[i].w); dfs4(j,0,b[i].w); 
			go.push_back(j); gow.push_back(b[i].w);
		}
	}
	cur=(atom2){1e18,1e18,0};
	for (int i=go.size();i;i--){
		int j=go[i-1];
		if (pd[j]==0){
			dfs3(j,0,gow[i-1]); dfs4(j,0,gow[i-1]);
		}
	}
	update(k,0);
	for (int i=p[k];i;i=b[i].next){
		int j=b[i].point;
		if (pd[j]==0) solve(j);
	}
}
int compare(atom k1,atom k2){
	return k1.w<k2.w;
}
int main(){
	scanf("%d",&n);
	for (int i=1;i<=n;i++) scanf("%d",&x[i]);
	for (int i=1;i<n;i++){
		int k1,k2,k3; scanf("%d%d%d",&k1,&k2,&k3);
		add(k1,k2,k3);
	}
	for (int i=1;i<=n;i++) father[i]=i;
	int rem=n; pren=n;
	while (rem>1){
		memset(pd,0x00,sizeof pd);
		for (int i=1;i<=n;i++) f[i]=1e18;
		solve(1); n=pren;
	//	cout<<"asd "<<ans<<endl;
	//	for (int i=1;i<=n;i++) cout<<father[i]<<" "; cout<<endl;
	//	for (int i=1;i<=n;i++) cout<<f[i]<<" "; cout<<endl;
	//	for (int i=1;i<=n;i++) cout<<whe[i]<<" "; cout<<endl;
		for (int i=1;i<=n;i++) A[i]=(atom){findfather(i),findfather(whe[i]),f[i]};
		sort(A+1,A+n+1,compare);
		for (int i=1;i<=n;i++){
			int k1=findfather(A[i].u),k2=findfather(A[i].v);
			if (k1!=k2){
				rem--; ans+=A[i].w; father[k1]=k2;
			}
		}
		for (int i=1;i<=n;i++) father[i]=findfather(father[i]);
	}
	cout<<ans<<endl;
	return 0;
}


Compiler output:
a.cc: In function 'int dfs1(int, int)':
a.cc:31:9: error: reference to 'size' is ambiguous
   31 |         size[k1]=1;
      |         ^~~~
In file included from /usr/include/c++/14/string:53,
                 from /usr/include/c++/14/bits/locale_classes.h:40,
                 from /usr/include/c++/14/bits/ios_base.h:41,
                 from /usr/include/c++/14/ios:44,
                 from /usr/include/c++/14/ostream:40,
                 from /usr/include/c++/14/iostream:41,
                 from a.cc:1:
/usr/include/c++/14/bits/range_access.h:272:5: note: candidates are: 'template<class _Tp, long unsigned int _Nm> constexpr std::size_t std::size(const _Tp (&)[_Nm])'
  272 |     size(const _Tp (&)[_Nm]) noexcept
      |     ^~~~
/usr/include/c++/14/bits/range_access.h:262:5: note:                 'template<class _Container> constexpr decltype (__cont.size()) std::size(const _Container&)'
  262 |     size(const _Container& __cont) noexcept(noexcept(__cont.size()))
      |     ^~~~
a.cc:14:53: note:                 'int size [210000]'
   14 | int p[N],len,x[N],father[N],whe[N],pd[N],n,pren,now,size[N],where;
      |                                                     ^~~~
a.cc:34:38: error: reference to 'size' is ambiguous
   34 |                 if (j!=k2&&pd[j]==0) size[k1]+=dfs1(j,k1);
      |                                      ^~~~
/usr/include/c++/14/bits/range_access.h:272:5: note: candidates are: 'template<class _Tp, long unsigned int _Nm> constexpr std::size_t std::size(const _Tp (&)[_Nm])'
  272 |     size(const _Tp (&)[_Nm]) noexcept
      |     ^~~~
/usr/include/c++/14/bits/range_access.h:262:5: note:                 'template<class _Container> constexpr decltype (__cont.size()) std::size(const _Container&)'
  262 |     size(const _Container& __cont) noexcept(noexcept(__cont.size()))
      |     ^~~~
a.cc:14:53: note:                 'int size [210000]'
   14 | int p[N],len,x[N],father[N],whe[N],pd[N],n,pren,now,size[N],where;
      |                                                     ^~~~
a.cc:36:16: error: reference to 'size' is ambiguous
   36 |         return size[k1];
      |                ^~~~
/usr/include/c++/14/bits/range_access.h:272:5: note: candidates are: 'template<class _Tp, long unsigned int _Nm> constexpr std::size_t std::size(const _Tp (&)[_Nm])'
  272 |     size(const _Tp (&)[_Nm]) noexcept
      |     ^~~~
/usr/include/c++/14/bits/range_access.h:262:5: note:                 'template<class _Container> constexpr decltype (__cont.size()) std::size(const _Container&)'
  262 |     size(const _Container& __cont) noexcept(noexcept(__cont.size()))
      |     ^~~~
a.cc:14:53: note:                 'int size [210000]'
   14 | int p[N],len,x[N],father[N],whe[N],pd[N],n,pren,now,size[N],where;
      |                                                     ^~~~
a.cc: In function 'void dfs2(int, int)':
a.cc:39:19: error: reference to 'size' is ambiguous
   39 |         int num=n-size[k1];
      |                   ^~~~
/usr/include/c++/14/bits/range_access.h:272:5: note: candidates are: 'template<class _Tp, long unsigned int _Nm> constexpr std::size_t std::size(const _Tp (&)[_Nm])'
  272 |     size(const _Tp (&)[_Nm]) noexcept
      |     ^~~~
/usr/include/c++/14/bits/range_access.h:262:5: note:                 'template<class _Container> constexpr decltype (__cont.size()) std::size(const _Container&)'
  262 |     size(const _Container& __cont) noexcept(noexcept(__cont.size()))
      |     ^~~~
a.cc:14:53: note:                 'int size [210000]'
   14 | int p[N],len,x[N],father[N],whe[N],pd[N],n,pren,now,size[N],where;
      |                                                     ^~~~
a.cc:43:37: error: reference to 'size' is ambiguous
   43 |                         num=max(num,size[j]); dfs2(j,k1);
      |                                     ^~~~
/usr/include/c++/14/bits/range_access.h:272:5: note: candidates are: 'template<class _Tp, long unsigned int _Nm> constexpr std::size_t std::size(const _Tp (&)[_Nm])'
  272 |     size(const _Tp (&)[_Nm]) noexcept
      |     ^~~~
/usr/include/c++/14/bits/range_access.h:262:5: note:                 'template<class _Container> constexpr decltype (__cont.size()) std::size(const _Container&)'
  262 |     size(const _Container& __cont) noexcept(noexcept(__cont.size()))
      |     ^~~~
a.cc:14:53: note:                 'int size [210000]'
   14 | int p[N],len,x[N],father[N],whe[N],pd[N],n,pren,now,size[N],where;
      |                                                     ^~~~
a.cc: In function 'void solve(int)':
a.cc:92:26: error: narrowing conversion of '1.0e+18' from 'double' to 'long long int' [-Wnarrowing]
   92 |         cur=(atom2){x[k],1e18,father[k]}; go.clear(); gow.clear();
      |                          ^~~~
a.cc:100:21: error: narrowing conversion of '1.0e+18' from 'double' to 'long long int' [-Wnarrowing]
  100 |         cur=(atom2){1e18,1e18,0};
      |                     ^~~~