Submission #2148281

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
typedef pair<int,ll> Q;
typedef pair<ll,P> P1;
typedef pair<P,P> P2;
#define pu push
#define pb push_back
#define mp make_pair
#define eps 1e-7
#define INF 1000000000
#define mod 1000000007
#define fi first
#define sc second
#define rep(i,x) for(int i=0;i<x;i++)
#define repn(i,x) for(int i=1;i<=x;i++)
#define SORT(x) sort(x.begin(),x.end())
#define ERASE(x) x.erase(unique(x.begin(),x.end()),x.end())
#define POSL(x,v) (lower_bound(x.begin(),x.end(),v)-x.begin())
#define POSU(x,v) (upper_bound(x.begin(),x.end(),v)-x.begin())
vector<Q>G[200005];
bool rem[200005]={};
int sub[200005]={},n,q;
vector<P1>edge;
ll a[200005];
int make(int v,int u)
{
    int cnt=1;
    for(int i=0;i<G[v].size();i++)
    {
        int v2=G[v][i].fi;
        if(rem[v2] || v2==u) continue;
        cnt+=make(v2,v);
    }
    return sub[v]=cnt;
}
P search(int v,int u,int siz)
{
    //size and index
    P res=mp(INF,-1);
    int s=1,m=0;
    for(int i=0;i<G[v].size();i++)
    {
        int v2=G[v][i].fi;
        if(rem[v2] || v2==u) continue;
        res=min(res,search(v2,v,siz));
        m=max(m,sub[v2]);
        s+=sub[v2];
    }
    m=max(m,siz-s);
    res=min(res,mp(m,v));
    return res;
}
vector<int>L;
pair<ll,int>p;
void dfs(int v,int u,ll d)
{
    p = min(p,mp(d+a[v],v));
    for(int i=0;i<G[v].size();i++)
    {
        int v2=G[v][i].fi;
        if(rem[v2] || v2==u) continue;
        dfs(v2,v,d+G[v][i].sc);
    }
}
void dfs2(int v,int u,ll d)
{
    edge.pb(mp(d+a[v]+p.fi,mp(v,p.sc)));
    for(int i=0;i<G[v].size();i++)
    {
        int v2=G[v][i].fi;
        if(rem[v2] || v2==u) continue;
        dfs2(v2,v,d+G[v][i].sc);
    }
}
void sol(int v)
{
    make(v,-1);
    int sz = sub[v];
    int cent=search(v,-1,sub[v]).sc;
    rem[cent]=true;
    L.clear(); L.pb(cent); p = mp(a[cent],cent);
    for(int i=0;i<G[cent].size();i++){
        if(!rem[G[cent][i].fi]) dfs(G[cent][i].fi,cent,G[cent][i].sc);
    }
    edge.pb(mp(a[cent]+p.fi,mp(cent,p.sc)));
    for(int i=0;i<G[cent].size();i++){
        if(!rem[G[cent][i].fi]) dfs2(G[cent][i].fi,cent,G[cent][i].sc);
    }
    for(int i=0;i<G[cent].size();i++) if(!rem[G[cent][i].fi]) sol(G[cent][i].fi);
    rem[cent]=false;
}
struct uf{
    int par[200005];
    void init(){ rep(i,200005) par[i]=i; }
    int find(int x){ if(x==par[x]) return x; else return par[x] = find(par[x]); }
    void unite(int x,int y){
        x = find(x); y = find(y);
        if(x == y) return;
        par[x] = y;
    }
    bool same(int x,int y){ return find(x) == find(y); }
}uf;
int main(){
    scanf("%d",&n);
    rep(i,n){
        scanf("%lld",&a[i]);
    }
    rep(i,n-1){
        int a,b; ll c; scanf("%d%d%lld",&a,&b,&c); a--; b--;
        G[a].pb(mp(b,c));
        G[b].pb(mp(a,c));
    }
    sol(0);
    ll ans = 0;
    SORT(edge); uf.init();
    rep(i,edge.size()){
        ll v = edge[i].fi; int p = edge[i].sc.fi, q = edge[i].sc.sc;
        if(uf.same(p,q)) continue;
        uf.unite(p,q); ans+=v;
    }
    cout<<ans<<endl;
}

Submission Info

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:106:19: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d",&n);
                   ^
./Main.cpp:108:28: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
         scanf("%lld",&a[i]);
                            ^
./Main.cpp:111:50: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
         int a,b; ll c; scanf("%d%d%lld",&a,&b,&c); a--; b--;
                                                  ^

Judge Result