题意简述

给定一棵树 $T=(V,E)$，其中 $V$ 为节点集合，$E$ 为边集合，对于 $V$ 中的每个节点 $v$，有一个权值函数 $W(v)$，该函数的值均为正整数，记 $d(u,v)$ 为节点 $u$ 和 $v$ 之间的距离，表示他们之间唯一的一条路径的边数。若 $u$ 和 $v$ 为同一个节点，则 $d(u,v)=0$。你的任务是找出两个不同的节点 $x,y$，使得以下表达式 $S(x,y)$ 最小：

$$S(x,y)=\sum\limits_{v\in V}(W(v)\times min(d(x,v),d(y,v))) $$

用人话讲就是：给定一颗无根数，在树中取两个点，让其他所有点「到这两个点的较小距离」的和最小。

思路分析

看题目第一眼，大部分人都会有个大致思路：

1. 将原树分成两个树；
2. 分别找到两个树的重心；
3. 求和。

分析一下复杂度，操作 $1$ 为 $O(n)$ 无疑，操作 $2,3$ 如果是 dfs 的话也是 $O(n)$。

显然 $O(n^2)$ 对于 $1 < N\le 5\times 10^4$ 这个数据范围来说实在是有点太大了，所以我们使用 DP 来做。

于是，枚举 $+$ DP，思路通。

方法解析

先来复习一下树的重心的性质：

重心是指树中的一个结点，如果将这个点删除后，剩余各个连通块中点数的最大值最小，那么这个节点被称为树的重心。

显然，「将重心删除后剩余各个连通块中点数的最大值」一定小于「树的总结点个数的一半」。

---

因此：

• 当我们在找重心时，若当前节点编号为 $u$，那么我们每次只要往 $u$ 的最大子树走即可；并且，只有当 $u$ 的「最大子树个数」$>$「此树总结点个数的一半」，我们才有继续走下去的必要。

于是，这样的时间复杂度就会大大降低，再加上一点预处理，便能够再足够短的时间内得出答案。

---

接下来看转移方程：

我们先人为设树的根节点为 $root$。

设「树中所有点到 $i$ 的价值之和」为 $dp_i$。

即「树中每一个点的点权 $\times$ 此点到 $i$ 的距离」 为 $dp_i$。

---

若 $t$ 是 $u$ 的子节点。

考虑：如何在已知 $dp_u$ 的情况下得出 $dp_t$。

通过思考我们可以发现，$t$ 相比 $u$，所有在 $u$ 这一边的节点都多走了一步，所有在 $t$ 这一边的节点都少走了一步。

设树中节点 $i$ 的子树的点权和（包括 $i$）为 $siz_i$，此树的总节点的点权和为 $cnt$。

那么：

• 所有在 $t$ 这一边的节点的点权和便为 $siz_t$；
  所有在 $u$ 这一边的节点的点权和便为 $cnt - siz_t$。

于是便可得转移方程：

$$siz_t = siz_u + (cnt - siz_t) - siz_t$$

即为：

$$siz_t = siz_u + cnt - 2 \times siz_t$$

---

我们再来考虑一些特殊情况：一个点的最大子树被切，导致其不再是最大子树。 这个其实很好考虑，只要再存储一个次大子树做「备胎」即可。

然后考虑，当一条边被砍掉之后会发生什么。

设在上面的树为 $A$，在下面的为 $B$。

易得：$A$ 中的 $siz$、$dp$ 均会发生变化。

我们还是设「断边」上面的节点为 $u$，下面的节点为 $t$。

对于 $siz$ 来说，$u$ 的所有「祖先节点」都失去了以 $t$ 为根的子树。

对于 $dp$ 来说，由于我们总是从一个根节点开始递归找重心，于是我们只要知道 $dp[1]$ 的变化值即可。

对于 $dp[1]$，先前有 $siz_t$ 个节点会走到 $root$，而现在没有了。

因此我们设 $i$ 节点的深度为 $dep_i$（$root$ 的深度为 $0$），则有：

$$dp[1] = dp[1] - siz_t \times dep_t$$

---

最后，我们要预处理的数组为：

• $dep_i$ —— $i$ 号节点的深度；
• $fa_i$ —— $i$ 号节点的父亲节点；
• $maxs_i$ —— $i$ 号节点的最大子树大小；
• $maxnum_i$ —— $i$ 号节点的最大子树编号；
• $remax_i$ —— $i$ 号节点的次大子树大小；
• $remaxnum_i$ —— $i$ 号节点的次大子树编号；
• $siz_i$ —— $i$ 号节点的所有子节点的权值之和；
• $dp_i$ —— 所有点到 $i$ 的价值之和。

AC代码

/* Code by Rosmarinus */

#include<iostream>
#include<vector>
#include<cstdio>
using namespace std;

const int N = 51000;
const int inf = 0x7f7f7f7f;

vector<int>side[N];
int val[N], dep[N], fa[N], maxs[N], maxnum[N], remax[N], remaxnum[N];
int siz[N], dp[N], d, ret;

void pre(int u, int father, int depth) // 预处理
{
    int S = side[u].size();
    fa[u] = father, siz[u] = val[u], dep[u] = depth;
    for(int i = 0; i < S; i ++)
    {
        int t = side[u][i];
        if(t == father) continue;

        pre(t, u, depth + 1);

        siz[u] += siz[t];
        dp[u] += dp[t] + siz[t];

        if(siz[t] > maxs[u])
        {
            remax[u] = maxs[u];
            remaxnum[u] = maxnum[u];
            maxs[u] = siz[t];
            maxnum[u] = t;
        }
        else if(siz[t] > remax[u])
        {
            remax[u] = siz[t];
            remaxnum[u] = t;
        }
    }
}

void dfs(int u, int s, int cnt)
{
    d = min(d, s);
    int t = maxnum[u];
    if(t == ret || siz[t] < siz[remaxnum[u]]) t = remaxnum[u]; // 之前的最大子树可能不再是现在的最大子树了
    if(t && 2 * siz[t] > cnt) dfs(t, s + cnt - 2 * siz[t], cnt);
}

int main()
{
    int n, x, y, ans = inf;

    scanf("%d", &n);

    for(int i = 1; i < n; i ++)
    {
        scanf("%d %d", &x, &y);
        side[x].push_back(y), side[y].push_back(x);
    }
    for(int i = 1; i <= n; i ++) scanf("%d", &val[i]);
    
    pre(1, 0, 0);
    
    for(int i = 2; i <= n; i ++)
    {
        for(int p = fa[i]; p > 0; p = fa[p]) siz[p] -= siz[i];
        d = inf, ret = i;

        dfs(1, dp[1] - dp[i] - siz[i] * dep[i], siz[1]);

        int a = d;
        d = inf;

        dfs(i, dp[i], siz[i]);
        ans = min(ans, a + d);

        for(int p = fa[i]; p > 0; p = fa[p]) siz[p] += siz[i];
    }

    cout << ans << endl;
    return 0;
}