Submission #8508150

---

Source Code Expand

#include <iostream>
#include <fstream>
#include <cstdio>
#include <cmath>
#include <vector>
#include <string>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <deque>
#include <bitset>
#include <algorithm>
#include <complex>
#include <array>
#include <functional>
using namespace std;
 
#define REP(i,n) for(int i=0; i<n; ++i)
#define FOR(i,a,b) for(int i=a; i<=b; ++i)
#define FORR(i,a,b) for (int i=a; i>=b; --i)
#define ALL(c) (c).begin(), (c).end()
 
typedef long long ll;
typedef vector<int> VI;
typedef vector<ll> VL;
typedef vector<double> VD;
typedef vector<VI> VVI;
typedef vector<VL> VVL;
typedef vector<VD> VVD;
typedef pair<int,int> P;
typedef pair<ll,ll> PL;

template<typename T> void chmin(T &a, T b) { if (a > b) a = b; }
template<typename T> void chmax(T &a, T b) { if (a < b) a = b; }

int in() { int x; scanf("%d", &x); return x; }
ll lin() { ll x; scanf("%lld", &x); return x; }

VI Centroid(VVI &graph){
    int n = graph.size();
    VI ret, sz(n);
    function<void (int, int)> dfs = [&](int now, int past){
        sz[now] = 1;
        bool is_centroid = true;
        for (int next : graph[now]){
            if (next == past) continue;
            dfs(next, now);
            sz[now] += sz[next];
            if (sz[next] > n / 2) is_centroid = false;
        }
        if (n - sz[now] > n / 2) is_centroid = false;
        if (is_centroid) ret.push_back(now);
    };
    dfs(0, -1);
    return ret;
}

const int N = 100010;
VI e[N];
VL c[N];
ll sz[N];

ll dfs(int now, int past){
    ll ret = 0;
    sz[now] = 1;
    REP(i,e[now].size()){
        int next = e[now][i];
        if (next == past) continue;
        ret += dfs(next, now);
        sz[now] += sz[next];
        ret += 2 * sz[next] * c[now][i];
        // cout << next << " " << sz[next] << " " << c[now][i] << endl;
    }
    return ret;
}

int main() {
    int n;
    cin >> n;
    VVI graph(n);
    REP(i,n-1){
        int x = in() - 1, y = in() - 1, z = in();
        e[x].push_back(y);
        c[x].push_back(z);
        e[y].push_back(x);
        c[y].push_back(z);
        graph[x].push_back(y);
        graph[y].push_back(x);
    }
    VI cs = Centroid(graph);
    ll ans = 0;
    if (cs.size() == 2){
        int c1 = cs[0], c2 = cs[1];
        ans = dfs(c1, c2) + dfs(c2, c1);
        REP(i,e[c1].size()){
            if (e[c1][i] == c2){
                ans += (n - 1) * c[c1][i];
            }
        }
    }else{
        int c1 = cs[0];
        ans = dfs(c1, -1) - *min_element(ALL(c[c1]));
    }
    cout << ans << endl;

    return 0;
}

Submission Info

Compile Error

./Main.cpp: In function ‘int in()’:
./Main.cpp:37:34: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
 int in() { int x; scanf("%d", &x); return x; }
                                  ^
./Main.cpp: In function ‘ll lin()’:
./Main.cpp:38:35: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
 ll lin() { ll x; scanf("%lld", &x); return x; }
                                   ^

Judge Result