洛谷 P2986 分析（别看）

科技起源

2026-07-16 20:46:27

发布于：河北

3阅读

0回复

0点赞

原题链接

1 题目

1.1 题目所需求出内容

对于本题，最终要求：一个最小值

1.2 题目背景、允许、禁止与限制

背景：有 $n$ 头奶牛圈，每个奶牛圈 $i$ 都有 $c_i$ 头奶牛。这些奶牛圈由 $n-1$ 条边连接，每条边 $i$ ， $a_i,b_i,l_i$ 分别代表起始奶牛圈，终止奶牛圈和两个奶牛圈之间的距离。
允许：在奶牛圈中设置一个集会，如果选择第 $x$ 头奶牛圈作为集会，那么不方便程度总和即为每个奶牛圈的奶牛数量 $c \times 到达集会的距离$
禁止：
限制：

1.3 题目数据范围与猜测

$1 \le n \le 10^5 \longrightarrow O(n)$

1.4 一句话概括题意

有被线路连接着的奶牛圈，设置一个集会，使得方便程度最大

2 题目破题推导

2.1 正向转逆向

方便程度最大 $\rightarrow$ 不方便程度最小

2.2 分情况考虑

对于某个节点 $u$ ，所有到它的不方便程度之和一定由两部分组成

第一个是 $u$ 的所有孩子到它
这个比较明了：就是到 $u$ 的所有子节点 $v$ 之和 $+$ 每个子节点 $v$ 为根时的子树的大小 $\times 每个节点v到节点u的距离$
第二个是 $v$ 除本身以外所有节点到它
这个又分四部分
- 第一部分： $u$ 到 $v$ 的距离 $\times v$ 为根时子树的大小
- 第二部分： $u$ 除了 $v$ 以外其他子节点的和（此时的“和”不包括除其他子节点为根时以外的节点）
- 第三部分：在所有 $u$ 的子节点（除了 $v$ ）全部集合到 $u$ 后，此时 $u$ 的大小 $\times u到v的距离$
- 第四部分：由于第一部分算上了 $v$ ，而我们现在尝试的是除 $v$ 以外，因此还要减掉 $以v为根子树的大小 \times u到v的长度$

3 模型匹配

格式为："关键词：...... $\longrightarrow$ $\huge{......}$ "

关键词：动态求取最小值，树上问题 $\longrightarrow$ $\huge{树形dp}$
注意在我们求 $v$ 除本身以外所有节点到它时，不能使用底下的答案，因此先更新答案再递归

4 最终代码（禁止抄袭，仅用于参考）

#include <bits/stdc++.h>
using namespace std;
#define int long long

int n;
const int N = 1e5 + 10;
int c[N];
struct node{
    int to;
    int w;
};
vector<node> g[N];
int sze[N];
int dp1[N], dp2[N];
void dfs_size(int u, int fa){
    sze[u] = c[u];
    for (node now : g[u]){
        if (now.to == fa) continue;
        dfs_size(now.to, u);
        sze[u] += sze[now.to];
    }
}
void dfs1(int u, int fa){
    for (node now : g[u]){
        if (now.to == fa) continue;
        dfs1(now.to, u);
        dp1[u] += dp1[now.to];
        dp1[u] += sze[now.to] * now.w;
    }
}
void dfs2(int u, int fa){
    for (node now : g[u]){
        if (now.to == fa) continue;
        dp2[now.to] = dp2[u] + (sze[1] - sze[u]) * now.w;
        dp2[now.to] += dp1[u] - dp1[now.to] + (sze[u] - sze[now.to]) * now.w - sze[now.to] * now.w;
        dfs2(now.to, u);
    }
}

signed main(){

    cin >> n;
    for (int i = 1;i <= n;i++){
        cin >> c[i];
    }
    for (int i = n + 2;i <= 2 * n;i++){
        int a, b, l;
        cin >> a >> b >> l;
        g[a].push_back({b, l});
        g[b].push_back({a, l});
    }
    dfs_size(1, -1);
    dfs1(1, -1);
    dfs2(1, -1);
    int mn = LLONG_MAX;
    for (int i = 1;i <= n;i++){
        mn = min(mn, dp1[i] + dp2[i]);
    }
    cout << mn;
    
    return 0;
}