Submission #2292802

---

Source Code Expand

#include<bits/stdc++.h>
#define maxn 200009
#define LL long long
#define pb push_back
using namespace std;
int a[maxn],sum,rt,f[maxn],sz[maxn],head[maxn],edge=0,fa[maxn];
bool vis[maxn];
LL dis[maxn];
struct da{
  int nex,to,w;
}e[maxn*2];
struct data{
  int x,y;LL w;
};
vector<data>E;
vector<int>vec;
inline void add(int from,int to,int w){
  e[++edge]=(da){head[from],to,w};
  head[from]=edge;
}
int find(int x){if(fa[x]!=x)fa[x]=find(fa[x]);return fa[x];}
void findrt(int x,int fa){
  f[x]=0,sz[x]=1;
  for(int i=head[x];i;i=e[i].nex){
    int v=e[i].to;
    if(v==fa || vis[v]) continue;
    findrt(v,x),sz[x]+=sz[v];
    f[x]=max(f[x],sz[v]);
  }
  f[x]=max(f[x],sum-sz[x]);
  if(f[x]<f[rt]) rt=x;
}
void dfs(int x,int fa){
  vec.pb(x);
  for(int i=head[x];i;i=e[i].nex) {
    int v=e[i].to;
    if(v==fa || vis[v]) continue;
    dis[v]=dis[x]+e[i].w;
    dfs(v,x);
  }
}
void solve(int x){
  vis[x]=1;vec.clear();
  dis[x]=0,dfs(x,0);int p=x;
  for(int i=0;i<vec.size();i++){
    dis[vec[i]]+=a[vec[i]];
    if(dis[vec[i]]<dis[p]) p=vec[i];
  }
  for(int i=0;i<vec.size();i++)
    E.pb((data){vec[i],p,dis[vec[i]]+dis[p]});
  for(int i=head[x];i;i=e[i].nex){
    int v=e[i].to;if(vis[v]) continue;
    sum=sz[v],rt=0,findrt(v,x);
    solve(rt);
  }
}
inline bool cmp(const data &A,const data &B){
  return A.w<B.w;
}
int main(){
  int n;
  scanf("%d",&n);
  for(int i=1;i<=n;i++) scanf("%d",a+i),fa[i]=i;
  for(int i=1,x,y,z;i<n;i++)
    scanf("%d%d%d",&x,&y,&z),add(x,y,z),add(y,x,z),E.pb((data){x,y,1ll*a[x]+a[y]+z});
  sum=n,rt=0,f[0]=1e9,findrt(1,0),solve(1);
  sort(E.begin(),E.end(),cmp);
  LL ans=0;
  for(int i=0;i<E.size();i++){
    int u=E[i].x,v=E[i].y;
    if(find(u)!=find(v)) ans+=E[i].w,fa[find(u)]=find(v);
  }
  printf("%lld\n",ans);
  return 0;
}

Submission Info

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:62:17: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d",&n);
                 ^
./Main.cpp:63:48: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
   for(int i=1;i<=n;i++) scanf("%d",a+i),fa[i]=i;
                                                ^
./Main.cpp:65:85: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d%d",&x,&y,&z),add(x,y,z),add(y,x,z),E.pb((data){x,y,1ll*a[x]+a[y]+z});
                                                                                     ^

Judge Result