BZOJ 1827 - [Usaco2010 Mar]gather 奶牛大集会

Published on 2016-04-10

题目地址

描述

Bessie正在计划一年一度的奶牛大集会,来自全国各地的奶牛将来参加这一次集会。当然,她会选择最方便的地点来举办这次集会。每个奶牛居住在 N(1N100,000)N(1\le N\le 100,000)个农场中的一个,这些农场由 N1N-1 条道路连接,并且从任意一个农场都能够到达另外一个农场。道路i连接农场 AiA_iBi(1AiN;1BiN) B_i(1 \le A_i \le N; 1 \le B_i \le N),长度为 Li(1Li1,000)L_i(1 \le L_i \le 1,000)。集会可以在 NN 个农场中的任意一个举行。另外,每个牛棚中居住者 Ci(0Ci1,000)C_i(0 \le C_i \le 1,000) 只奶牛。在选择集会的地点的时候,Bessie希望最大化方便的程度(也就是最小化不方便程度)。比如选择第 XX 个农场作为集会地点,它的不方便程度是其它牛棚中每只奶牛去参加集会所走的路程之和,(比如,农场 ii 到达农场 XX 的距离是 20,那么总路程就是 Ci20C_i*20。帮助 Bessie找出最方便的地点来举行大集会。
考虑一个由五个农场组成的国家,分别由长度各异的道路连接起来。在所有农场中,3 号和 4 号没有奶牛居住。

样例输入

5
1
1
0
0
21 3 1
2 3 2
3 4 3
4 5 3

样例输出

15

分析

暴力的话 O(n2)O(n^2) 铁定爆炸,我们考虑已经求得一个点 uu 的答案,如何快速得到它的某个儿子 vv 的答案。
假设 uu 的答案是 dis[u]dis[u],那么集会点移到 vv,对于所有的奶牛来说只有 2 种情况:

  1. 到集会点的距离变长
  2. 到集会点的距离变短

容易发现的是,无论变长还是变短,每个奶牛只会多/少走 cost(u,v)\text{cost}_{(u, v)}。而且只有处于 vv 及其子树的牛会减,其余的都会加,所以很容易转移答案。
所以先求出根的答案,再次 dfs 即可。

代码

//  Created by Sengxian on 4/10/16.
//  Copyright (c) 2016年 Sengxian. All rights reserved.
//  BZOJ 1827 树形DP
#include <algorithm>
#include <iostream>
#include <cctype>
#include <climits>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <vector>
#include <queue>
using namespace std;

inline int ReadInt() {
    static int n, ch;
    n = 0, ch = getchar();
    while (!isdigit(ch)) ch = getchar();
    while (isdigit(ch)) n = (n << 3) + (n << 1) + ch - '0', ch = getchar();
    return n;
}

typedef long long ll;
const int maxn = 100000 + 3;
struct edge {
    int to, cost;
    edge(int to, int cost): to(to), cost(cost) {}
};
vector<edge> G[maxn];
ll dis[maxn], ans = 1LL << 60;
int s[maxn], cnt[maxn], n;

int dfs(int u, int fa, int d) {
    s[u] = cnt[u], dis[0] += (ll)cnt[u] * d;
    for (int i = 0; i < G[u].size(); ++i) {
        edge &e = G[u][i];
        if (e.to != fa) s[u] += dfs(e.to, u, d + e.cost);
    }
    return s[u];
}

void dfs(int u, int fa) {
    ans = min(ans, dis[u]);
    for (int i = 0; i < G[u].size(); ++i) {
        edge &e = G[u][i];
        if (e.to != fa) {
            dis[e.to] = dis[u] + (ll)e.cost * (s[0] - s[e.to] * 2);
            dfs(e.to, u);
        }
    }
}

int main() {
    n = ReadInt();
    for (int i = 0; i < n; ++i) cnt[i] = ReadInt();
    for (int i = 0; i < n - 1; ++i) {
        int f = ReadInt() - 1, t = ReadInt() - 1, c = ReadInt();
        G[f].push_back(edge(t, c));
        G[t].push_back(edge(f, c));
    }
    dfs(0, -1, 0);
    dfs(0, -1);
    printf("%lld\n", ans);
    return 0;
}