AOJ 1196: 橋の撤去 / Bridge Removal
$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;
}