题目描述

难度分:$1347$

输入$n(1 \leq n \leq 10^5)$。

输入一棵无向树的$n-1$条边，边权为$1$，节点编号从$1$到$n$。

输入长为$n$的数组$a(1 \leq a[i] \leq 10^9)$。

定义$f(x)=\Sigma_{i=1}^{n}dist(x, i) \times a[i]$，其中$dist(x, i)$表示$x$到$i$的最短路长度。

输出$f(1)$，$f(2)$，……，$f(n)$中的最小值。

输入样例$1$

4
1 2
1 3
2 4
1 1 1 2

输出样例$1$

5

输入样例$2$

2
2 1
1 1000000000

输出样例$2$

1

输入样例$3$

7
7 3
2 5
2 4
3 1
3 6
2 1
2 7 6 9 3 4 6

输出样例$3$

56

算法

换根DP

非常明显的一个换根DP，定义两个数组$w$和$f$，$w[u]$表示以$u$为根节点的子树所有节点的$a[i]$之和。

动态规划

状态定义

$f[u]$表示以$u$为根的子树中，所有子节点到$u$的$f$值。这样一来，就可以先随便定一个根，比如$1$，从$1$开始进行DFS计算出一个初始的$f$数组和$w$数组。

状态转移

假设$v$是$u$的子节点，那么$u$子数中所有子孙节点到$u$的$f$值为$f[u]=\Sigma_{v}f[v]+w[v]$。含义是“子树$v$中的所有节点先到$v$，即f[v]$。再从$v$向上走一步到达$u$，加上子树$v$中所有节点的权值$w[v]$”。

DFS换根

从$1$开始，换根计算以$u$为整个树的根时，$f$值会如何变化。定义递归函数$dfs(u, vx)$，$u$是当前节点，$vx$表示$u$上面所有节点到$u$的$f$值。那么最终答案就应该$min_{u=1}^{n}(f[u]+vx_{u})$。

还是遍历$u$的所有子节点$v$，当以$v$为整棵树的根时，我们需要计算$v$的$vx$。一部分是$u$上面所有节点的贡献$vx$，另一部分是$f[u]$中除去$v$子树的贡献$f[u]-f[v]-w[v]$（即$v$的兄弟子树贡献）。这些节点到$u$的$f$值就是$f[u]-f[v]-w[v]+vx$，它们到达$u$之后还需要算上节点$u$往$v$再走一步，所以还需要加上$\Sigma_{i=1}^{n}a[i]-w[v]=w[1]-w[v]$，也就说明$vx_v=f[u]-f[v]-w[v]+vx_u+w[1]-w[v]$。

这时候我们只需要DFS遍历整棵树，维护$f[u]+vx_u$的最小值就可以了。

复杂度分析

时间复杂度

换根DP本质上就是对整棵树DFS遍历两遍，时间复杂度为$O(n)$。

空间复杂度

子树的权值和数组$w$空间消耗是线性的；子树中所有节点到根节点的$f$值数组$f$空间消耗也是线性的；树的邻接表空间复杂度还是线性的。除此之外，在算法过程中DFS在整棵树退化为链的情况下，最大递归深度为$O(n)$。因此，整个算法的额外空间复杂度为$O(n)$。

C++ 代码

#include <bits/stdc++.h>

using namespace std;
typedef long long LL;

const int N = 100010;
int n, a[N];
vector<int> graph[N];
LL f[N], w[N], ans;

void dfs1(int u, int fa) {
    w[u] = a[u];
    for(int v: graph[u]) {
        if(v == fa) continue;
        dfs1(v, u);
        w[u] += w[v];
        f[u] += f[v] + w[v];
    }
}

void dfs2(int u, int fa, LL vx) {
    ans = min(ans, f[u] + vx);
    for(int v: graph[u]) {
        if(v == fa) continue;
        dfs2(v, u, vx + f[u] - f[v] - w[v] + w[1] - w[v]);
    }
}

int main() {
    scanf("%d", &n);
    for(int i = 1; i <= n; i++) {
        graph[i].clear();
        f[i] = w[i] = 0;
    }
    for(int i = 1; i < n; i++) {
        int u, v;
        scanf("%d%d", &u, &v);
        graph[u].push_back(v);
        graph[v].push_back(u);
    }
    for(int i = 1; i <= n; i++) {
        scanf("%d", &a[i]);
    }
    dfs1(1, 0);
    ans = 9e18;
    dfs2(1, 0, 0);
    printf("%lld\n", ans);
    return 0;
}