闲话

原来上一个写的题目叫做换根 dp 啊，之前还以为就是一个技巧，还真的有名字啊原来。

题目大意

给出一颗有边权也有点权的树。选择一个点作为根，不妨设它为 $x$。之后设一个值为每一个结点的点权乘上这个结点到 $x$ 的边权之和。然后把每一个节点的值加起来，使这个值最小，输出这个值。

$1\leq n\leq 10^5$

思路

首先暴力思路很明显，就是遍历每一个结点之后遍历整棵树作为答案然后求最小值即可。时间复杂度 $O(n^2)$。考虑优化。

换根 dp

首先我们引进一个换根 dp 的概念。换根 dp 是一种树型 dp，又叫二次扫描，至于为什么要叫二次扫描一会儿就知道了。换根 dp 通常有下面的几个性质：

• 在已树上的不同点为根时答案是不同的。
• 求答案时不能随机定一个结点为根了，要去求每一个结点为根时的信息。
• 无法一次遍历直接求出答案，所以暴力做法至少是 $O(n^2)$ 的。

我们怎么做呢？

先给出一个基本的思考步骤，之后一个一个的说。

• 先随意确定一个点为根。
• 之后的第一次扫描（dfs），求出我们选择的根的答案，同时做一些因题而异的预处理（如子树大小）。
• 再进行第二次扫描，以我们这个点的值往下推进，进而求出每一个点的值。

第一步，我们就以 $1$ 为根好了。

之后进行第二步的扫描，我们首先可以定义出 $dp[u]$ 为 $u$ 的子树（包括 $u$）的答案。暂时我们可以先记这么多，因为预处理的部分我们暂时还不知道应该记录什么。

之后第三步，我们往下推。先写出来一个假式子之后再往里填公式。

$dp[v]=dp[u]$

这肯定是不对的，我们画个图看看。

我们画完图可以发现，$dp[u]$ 包含了 $v$ 和它的子树。所以我们应该减去。我们应该减去 $num[v]*e(u,v)$，也就是 $v$ 的子树的元素个数之和（包括 $v$）。这个就可以放到预处理来做了。

但还没有完事，$c$ 可没有经过 $e(u,v)$，所以应该除了 $v$ 和其子树之外的元素点权之和再乘上 $e(u,v)$。我们总结一下：

$dp[v]=dp[u]-num[v]\times e(u,v)+(sum-num[v])\times e(u,v)$

代码

#include <iostream>

using namespace std;
typedef long long ll;
const ll MAXN = 1e5 + 5;
const ll INF = 1e55 + 1;
ll c[MAXN], num[MAXN], dp[MAXN], sum;
struct edge {
    ll to, weight, nxt;
} e[MAXN * 2];
ll head[MAXN], tot;

void add(ll u, ll v, ll w) {
    e[++tot].nxt = head[u];
    e[tot].to = v;
    e[tot].weight = w;
    head[u] = tot;
}

void dfs(ll u, ll f) {
    num[u] = c[u];
    for (ll i = head[u]; i; i = e[i].nxt) {
        ll v = e[i].to, w = e[i].weight;
        if (v == f) {
            continue;
        }
        dfs(v, u);
        num[u] += num[v];
        dp[u] += dp[v] + num[v] * w;
    }
}

void DP(ll u, ll f) {
    for (ll i = head[u]; i; i = e[i].nxt) {
        ll v = e[i].to, w = e[i].weight;
        if (v == f) {
            continue;
        }
        dp[v] = dp[u] - num[v] * w + (sum - num[v]) * w;
        DP(v, u);
    }
}

int main() {
    ll n;
    scanf("%lld", &n);
    for (int i = 1; i <= n; ++i) {
        scanf("%lld", &c[i]);
        sum += c[i];
    }
    for (int i = 1; i <= n - 1; ++i) {
        ll u, v, w;
        scanf("%lld%lld%lld", &u, &v, &w);
        add(u, v, w);
        add(v, u, w);
    }
    dfs(1, 0);
    ll ans = INF;
    DP(1, 0);
    for (int i = 1; i <= n; ++i) {
        ans = min(ans, dp[i]);
    }
    printf("%lld\n", ans);
    return 0;
}
复制代码

总结

知道了一种新的树形 dp 技巧 换根 dp，同时分析了换根 dp 的做法还有换根 dp 类题目的套路。