Submission #1452631

---

Source Code Expand

#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<b;i++)
#define rrep(i,a,b) for(int i=a;i>=b;i--)
#define fore(i,a) for(auto &i:a)
#pragma GCC optimize ("-O3")
using namespace std; void _main(); int main() { cin.tie(0); ios::sync_with_stdio(false); _main(); }
//---------------------------------------------------------------------------------------------------
/*---------------------------------------------------------------------------------------------------
　　　　　　　　　　　 ∧＿∧  
　　　　　 ∧＿∧ 　（´<_｀ ）　 Welcome to My Coding Space!
　　　　 （ ´_ゝ`）　/　 ⌒i     
　　　　／　　　＼　 　  |　|     
　　　 /　　 /￣￣￣￣/　　|  
　 ＿_(__ﾆつ/　    ＿/ .| .|＿＿＿＿  
　 　　　＼/＿＿＿＿/　（u　⊃  
---------------------------------------------------------------------------------------------------*/





typedef long long ll;
int N, A[101010], B[101010], C[101010];
//---------------------------------------------------------------------------------------------------
map<pair<int, int>, int> dic;
vector<int> E[101010];
int S[101010];
int cnt[101010], dep[101010];
void dfs(int cu, int pa = -1) {
    cnt[cu] = 1;
    fore(to, E[cu]) if (to != pa) {
        dep[to] = dep[cu] + 1;
        dfs(to, cu);
        cnt[cu] += cnt[to];
    }
}
int count(int from, int to) { // from -> toと遷移するとき、to以降の頂点数
    if (dep[from] < dep[to]) return cnt[to];
    else return N - cnt[from];
}
//---------------------------------------------------------------------------------------------------
ll case1(int edgeid) { // Si = N/2 となる辺がある場合
    ll ans = 0;
    rep(i, 0, N - 1) ans += 1LL * C[i] * 2 * S[i];
    ans -= C[edgeid];
    return ans;
}
//---------------------------------------------------------------------------------------------------
ll case2() { // Si = N/2 となる辺がない場合
    int centroid;
    rep(cu, 0, N - 1) {
        int ok = 1;
        fore(to, E[cu]) {
            int c = count(cu, to);
            if (N / 2 < c) ok = 0;
        }
        if (ok) {
            centroid = cu;
            break;
        }
    }

    ll ans = 0;
    rep(i, 0, N - 1) ans += 1LL * C[i] * 2 * S[i];
    ll mi = 1LL<<60;
    fore(to, E[centroid]) {
        int i = dic[{centroid, to}];
        mi = min(mi, (ll)C[i]);
    }
    return ans - mi;
}
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N;
    rep(i, 0, N - 1) {
        cin >> A[i] >> B[i] >> C[i];
        A[i]--; B[i]--;
        E[A[i]].push_back(B[i]);
        E[B[i]].push_back(A[i]);
        dic[{A[i], B[i]}] = dic[{B[i], A[i]}] = i;
    }

    dfs(0);

    int ok = -1;
    rep(i, 0, N - 1) {
        int c = count(A[i], B[i]);
        S[i] = min(c, N - c);
        if (S[i] * 2 == N) ok = i;
    }

    ll ans;
    if (0 <= ok) ans = case1(ok);
    else ans = case2();
    cout << ans << endl;
}

Submission Info

Judge Result