http://agc018.contest.atcoder.jp/tasks/agc018_d
解説放送・公式解説
解説
http://agc018.contest.atcoder.jp/submissions/1452631
pdfの公式解説の副読本としての解説です。
今回は適切に始点を決めることで、最適な動きが達成できるのを（恐らく決め打ちで）探していく問題。
2通りの場合分けがあるが、使う関数について説明しておく。
count(from,to) := 頂点fromから頂点toへの方向を考えたときに、to側での部分木の頂点数
これは前もってdfsをして、ある根(実装では頂点0を根としている)からの深さと部分木の個数を求めておくことでO(1)で高速に求めることができる。
これを使ってS[i]を事前計算しておく。
S[i] = N/2となる辺がある場合(case1関数)
これは、ある辺について考えたときに両端の頂点数が同数になる場合を意味する。
そのため、S[i]*2=Nである場合というのが正しい。
この場合はこの辺のみ「最適回数-1」回しか選択できない（これは放送・解説参照）。
その為、最善-この辺のコストをすると答え。
S[i] = N/2となる辺がない場合(case2関数)
上ではない時はこっちで答えを出す。
木の重心を求めるとあるが、今回は木の重心とはちょっと違う様な気がする（要確認）。
今回は中心とする頂点を見つけるが、これは、その頂点から伸びる辺でつながる部分木のそれぞれの頂点数がN/2以下である頂点のことである。
自分の実装ではこれを愚直にチェックして求めている。
この場合は、中心とする頂点から遷移される辺のうち1つの辺のみ「最適回数-1」回となる。
どれでも良いのだが、一番コストの小さいものを-1回するのが適切だというのは自明。
その為、最善-中心とする頂点から遷移される辺のうち最小コストをすると答え。
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; }
