ICPC国内予選2014E: 橋の撤去/Bridge Removal

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1196&lang=ja

問題

頂点辺からなるグラフ(つまり木)が与えられる。
最初、好きな島に居るとして繰り返し以下のいずれかの操作が可能。

• 今いる頂点の隣の頂点に移動する。
• 今いる頂点に生えている辺を削除する。

ただし、いずれの操作も辺の重みだけのコストがかかる。
全ての辺を削除するのに必要な最短時間を求めよ。

解法

まず、下のような部分木について考えると全ての辺を削除するのに葉に行く必要は無いことと、合計で3回の操作が必要な辺が存在することがわかります。
また、この時点ではほとんどの辺には3回の操作が必要ではないかという予感がします。(後に外れます)

もう少し考察を進めるために、先ほどの図では無視していた右側の部分木を付け加えて考えると、適当に選んだPathに含まれる辺は2回の操作で済む事がわかります。

以上の考察より次の事実がわかります。

• 葉となっている頂点から生えている辺は1回の操作で済む。
• 葉では無い頂点uを始点に、頂点vを終点にもつPathに含まれる辺は2回の操作で済む。
• 上記以外の辺は3回の操作で削除できる。

ここまで来ると、どんな頂点をu, vとして選べばよいかが気になります。出来るだけ得をしたいのでuとvの距離が大きいとうれしいです。
制約が小さいのでuとvを総当りしても良いですが、が最大は木の直径だということに気づけます。(ググると良い記事がいっぱいあります！)
頂点u, vは葉では無い事を上で断っていることに注意すると、葉を取り除いた後のグラフの直径を求めれば良い事がわかります。

よって、これまでの事をまとめると答えは次の式で表せます。

実装

実装についての話をメモ書き程度ですが書いておきます。(自分用なのでちょっと適当かも、パッとコードが読めないんですよね・・・悲しい・・・)
まず、重みつきグラフを受け取ります。その際にまとめて辺の和を3倍したものを求めてしまいます。
次に、葉を削除します。葉は次数1の頂点のことなので簡単に見つける事が出来ます。ついでに葉に繋がった辺を2倍して引いてあげます。
あとは削除した頂点がスタート地点では困るので、スタート地点をいい感じにしてdouble sweepで直径を求めます。
(適当選んだ頂点sから一番遠い頂点uを調べて、今度は頂点uから一番遠い頂点vを見つけると、u, vが直径になってるってやつです。)
最後に、直径を答えから引いたら考察の最後に書いた式を計算できています。無事終了です。

コード

AIZU ONLINE JUDGE: Code Review

using P = pair<int, int>;
const int INF = 1e9;

int n;
vector<vector<P>> G;
vector<int> leaves;


vector<int> calc_distance(int start) {
    vector<int> dist(n, INF);
    dist[start] = 0;

    function<void(int, int)> dfs = [&](int v, int p) {
        for (auto x : G[v]) {
            int nv = x.first;
            int w = x.second;
            if (nv == p) continue;
            if (!leaves[nv]) {
                dist[nv] = dist[v] + w;
                dfs(nv, v);
            }
        }
    };
    dfs(start, -1);

    return dist;
}


void solve() {

    int ans = 0;

    vector<int> tmp(n - 1);
    for (int i = 0; i < n - 1; i++) cin >> tmp[i];

    //重みつきグラフを受け取る
    G.assign(n + 1, vector<P>());
    for (int i = 1; i < n; i++) {
        int w; cin >> w;
        int to = tmp[i-1] - 1;
        ans += 3 * w;
        G[i].push_back(P{ to, w });
        G[to].push_back(P{ i, w });
    }

    //葉を除去する
    leaves.assign(n, 0);
    for (int i = 0; i < n; i++) {
        if (G[i].size() == 1) {
            leaves[i] = 1;
            ans -= 2 * G[i][0].second;
        }
    }


    //すでに除去した頂点がスタート地点になっているとき変更する
    int start = 0;
    while (leaves[start]) {
        start++;
    }


    //startから一番遠い点uを求める
    int u = start;
    auto dist_u = calc_distance(start);
    for (int i = 0; i < n; i++) {
        if (!leaves[i] && dist_u[i] > dist_u[u]) u = i;
    }

    //uから一番遠い点vを求める
    int v = start;
    auto dist_v = calc_distance(u);
    for (int i = 0; i < n; i++) {
        if (!leaves[i] && dist_v[i] > dist_v[v]) v = i;
    }
    
    //uとvの距離(木の直径)
    int diameter = dist_v[v];
    ans -= diameter;

    cout << ans << endl;
}


int main() {
    while (1) {
        cin >> n;
        if (n == 0) break;
        solve();
    }
}