Submission #2510220

---

Source Code Expand

#include<stdio.h>
#include<vector>
#include<algorithm>
using namespace std;
typedef long long ll;
struct edge{
	int x,y;
	ll v;
	edge(int a=0,int b=0,ll c=0){x=a;y=b;v=c;}
};
bool operator<(edge a,edge b){return a.v<b.v;}
vector<edge>e;
int h[200010],nex[400010],to[400010],w[400010],v[200010],M;
void add(int a,int b,int c){
	M++;
	to[M]=b;
	w[M]=c;
	nex[M]=h[a];
	h[a]=M;
}
bool vis[200010];
int siz[200010],n;
void dfs1(int fa,int x){
	siz[x]=1;
	n++;
	for(int i=h[x];i;i=nex[i]){
		if(!vis[to[i]]&&to[i]!=fa){
			dfs1(x,to[i]);
			siz[x]+=siz[to[i]];
		}
	}
}
int mn,cn;
ll d[200010];
void dfs2(int fa,int x){
	int i,k;
	k=0;
	for(i=h[x];i;i=nex[i]){
		if(!vis[to[i]]&&to[i]!=fa){
			dfs2(x,to[i]);
			k=max(k,siz[to[i]]);
		}
	}
	k=max(k,n-siz[x]);
	if(k<mn){
		mn=k;
		cn=x;
	}
}
vector<int>q;
void dfs3(int fa,int x){
	q.push_back(x);
	for(int i=h[x];i;i=nex[i]){
		if(!vis[to[i]]&&to[i]!=fa){
			d[to[i]]=d[x]+w[i];
			dfs3(x,to[i]);
		}
	}
}
void solve(int x){
	int i,t;
	ll mn;
	n=0;
	dfs1(0,x);
	::mn=2147483647;
	dfs2(0,x);
	x=cn;
	q.clear();
	d[x]=0;
	dfs3(0,x);
	mn=9223372036854775807ll;
	for(int x:q){
		d[x]+=v[x];
		if(d[x]<mn){
			mn=d[x];
			t=x;
		}
	}
	for(int x:q)e.push_back(edge(t,x,d[t]+d[x]));
	vis[x]=1;
	for(i=h[x];i;i=nex[i]){
		if(!vis[to[i]])solve(to[i]);
	}
}
int fa[200010];
int get(int x){return fa[x]==x?x:(fa[x]=get(fa[x]));}
int main(){
	int n,i,a,b,c;
	ll ans;
	scanf("%d",&n);
	for(i=1;i<=n;i++)scanf("%d",v+i);
	for(i=1;i<n;i++){
		scanf("%d%d%d",&a,&b,&c);
		add(a,b,c);
		add(b,a,c);
	}
	solve(1);
	sort(e.begin(),e.end());
	for(i=1;i<=n;i++)fa[i]=i;
	ans=0;
	for(edge t:e){
		a=get(t.x);
		b=get(t.y);
		if(a!=b){
			fa[a]=b;
			ans+=t.v;
		}
	}
	printf("%lld",ans);
}

Submission Info

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:90:16: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&n);
                ^
./Main.cpp:91:34: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
  for(i=1;i<=n;i++)scanf("%d",v+i);
                                  ^
./Main.cpp:93:27: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d%d",&a,&b,&c);
                           ^

Judge Result