Submission #6420034

---

Source Code Expand

#include<bits/stdc++.h>
using namespace std;

#define FOR(i, a, b) for(int i = a; i < b; ++i)
#define REP(i, n) FOR(i, 0, n)
#define _ << " " <<
#define sz(x) ((int) x.size())
#define pb(x) push_back(x)
#define TRACE(x) cerr << #x << " = " << x << endl

typedef long long ll;
typedef pair<int, int> point;

const int MAXN = 1e5 + 5;

int n, sz[MAXN];
vector <point> E[MAXN];
ll dist[MAXN], sol;
vector <int> centroid;

void dfs(int x, int p) {
  sz[x] = 1;
  int mx = 0;
  for (auto e : E[x]) {
    if(e.first == p) continue;

    dfs(e.first, x);
    sz[x] += sz[e.first];
    mx = max(mx, sz[e.first]);
  }

  if(max(mx, n - sz[x]) <= n / 2)
    centroid.push_back(x);
}

void dfs_dist(int x, int p = -1){
  sz[x] = 1;
  for(auto e : E[x]){
    if(e.first == p) continue;
    dist[e.first] = dist[x] + e.second;
    dfs_dist(e.first, x);
    sol += 2LL * e.second * min( sz[e.first], n - sz[e.first] );
    sz[x] += sz[e.first];
  }
}

ll solve(int x){
  sol = 0;
  dfs_dist(x);

  ll mn = 1e18;
  for(auto e : E[x])
    mn = min(mn, (ll)e.second);

  if(sz(centroid) == 1)
    return sol - mn;

  for(auto e : E[x])
    if(e.first == centroid[0] || e.first == centroid[1])
      return sol - e.second;
}

int main(){
  ios_base::sync_with_stdio(false); cin.tie(0);

  cin >> n;
  REP(i, n - 1){
    int a, b, c;
    cin >> a >> b >> c;
    a --; b --;
    E[a].pb(point(b, c));
    E[b].pb(point(a, c));
  }

  dfs(0, 0);
  ll sol = 1e18;
  for(auto it : centroid)
    sol = min(sol, solve(it));
  cout << sol;
}

Submission Info

Judge Result