这里还没有题解诶……那我来写一个

话说这道题好像也没人做诶

一.题意分析

这道题目让我们求的是：

$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 50000$ 这个数据范围来说实在是有点太大了，所以我们使用 $DP$ 来做。

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

三.方法解析

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

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

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

下面是分析，懂的可跳过……算了我不分析了大家自己感觉一下吧……我觉得可以用 正确性显然法。

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

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

接下来看转移方程：

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

设 树中所有点到i的价值之和（即每一个点的点权×此点到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代码

我觉得应该不需要过多注释，至少对于我代码的可读性我还是有自信的。

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

const int N = 51000, 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 re(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;
        re(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]);
    }

    re(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;
}

Made by $\operatorname{Rosmarinus}$

希望能对你有所帮助