AOJ 1196: 橋の撤去 / Bridge Removal

,

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

$N = 800$だがWarshall-Floydしたら間に合わないらしい。

solution

(答え) = (重みの総和) + 2 $\times$ (葉に繋がっていない辺の重み) - (葉を通らないpathの最短路長)。 橋の撤去のコストは必ずかかるので、移動のコストだけ考えればよい。 葉に移動する必要はなく、ほとんどの辺はちょうど$2$度通る。好きにひとつpathを選んで、それだけは$1$度だけ通るようにできるので、そのような最大を求めればよい。 $O(N^2)$。

implementation

#include <cstdio>
#include <functional>
#include <numeric>
#include <tuple>
#include <vector>
#define repeat(i, n) for (int i = 0; (i) < int(n); ++(i))
#define whole(f, x, ...) ([&](decltype((x)) whole) { return (f)(begin(whole), end(whole), ## __VA_ARGS__); })(x)
using namespace std;
template <class T> inline void setmax(T & a, T const & b) { a = max(a, b); }
template <typename X, typename T> auto vectors(X x, T a) { return vector<T>(x, a); }
template <typename X, typename Y, typename Z, typename... Zs> auto vectors(X x, Y y, Z z, Zs... zs) { auto cont = vectors(y, z, zs...); return vector<decltype(cont)>(x, cont); }

int main() {
    while (true) {
        int n; scanf("%d", &n);
        if (n == 0) break;
        vector<int> p(n-1); repeat (i, n-1) { scanf("%d", &p[i]); -- p[i]; }
        vector<int> d(n-1); repeat (i, n-1) scanf("%d", &d[i]);
        vector<vector<pair<int, int> > > g(n);
        repeat (i, n-1) {
            g[i+1].emplace_back(p[i], d[i]);
            g[p[i]].emplace_back(i+1, d[i]);
        }
        auto dist = vectors(n, n, -1);
        repeat (root, n) {
            function<void (int)> dfs = [&](int i) {
                for (auto e : g[i]) {
                    int j, d; tie(j, d) = e;
                    if (dist[root][j] == -1) {
                        dist[root][j] = dist[root][i] + d;
                        dfs(j);
                    }
                }
            };
            dist[root][root] = 0;
            dfs(root);
        }
        int longest = 0;
        repeat (i, n) if (g[i].size() >= 2) {
            repeat (j, n) if (g[j].size() >= 2) {
                setmax(longest, dist[i][j]);
            }
        }
        int d_sum = whole(accumulate, d, 0);
        int d_leaf = 0;
        repeat (i, n) if (g[i].size() == 1) {
            d_leaf += g[i][0].second;
        }
        int result = 3 * d_sum - 2 * d_leaf - longest;
        printf("%d\n", result);
    }
    return 0;
}