洛谷 P3931 分析（别看）

科技起源的小号1

2026-10-01 17:30:55

发布于：天津

3阅读

0回复

0点赞

原题链接

1 题目

1.1 题目所需求出内容

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

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

背景：
一棵树有 $n$ 个点和一个给定的树根 $root$
一条边 $(a,b,c)$ 表示 $a,b$ 两点间有一条边权为 $c$ 的边

允许：
求割开这棵树的最小代价

割开一棵有根树：删除若干条边，使得任何叶子节点和根节点不连通
割一条边的代价就是这条边的边权

1.3 题目数据范围与猜测

$n \le 10^5, c \le 10^6\longrightarrow O(n)$

1.4 一句话概括题意

给定一棵有根树，求割开这棵树的最小代价

2 题目破题推导

2.1 第一步：分情况讨论

对于每个不为叶子节点的点，为了使其子孙中的叶子结点与根节点断开，有两种操作可选

让子树内部断
自己连着子树的这条边断

但是会引出一个问题：要是全程不断（因为这样无花费）怎么办
可以将初始不断的花费设置为 $\infty$ ，这样不论如何总得断一条

3 模型匹配

比较简单的树形dp
主要：

排除叶子结点（没法转移）
根节点是给定的，而非 $1$
每个节点的所有子树断开代价要累加（每个子树是 $max(子树若自身断开代价,子树与该点连接的那条边断开的代价)$ ）

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

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

inline int read(){
    int num = 0;
    int f = 1;
    char ch = getchar();
    while(ch < '0' || ch > '9'){
        if (ch == '-'){
            f = -1;
        }
        ch = getchar();
    }
    while(ch >= '0' && ch <= '9'){
        num = (num << 3) + (num << 1) + (ch ^ 48);
        ch = getchar();
    }
    return num * f;
}

int n;
const int N = 111111;
int root;
struct node{
    int to;
    int w;
};
vector<node> g[N];
int dp[N];
const int INF = 111111111111111;
void dfs(int u, int fa){
    dp[u] = INF;
    bool is_leaf = true;
    for (node v : g[u]){
        if (v.to != fa){
            is_leaf = false;
            break;
        }
    }
    if (is_leaf) return ;
    int temp = 0;
    for (node v : g[u]){
        if (v.to == fa) continue;
        dfs(v.to, u);
        temp += min(dp[v.to], v.w);
    }
    dp[u] = min(dp[u], temp);
}

signed main(){

    n = read(), root = read();
    for (int i = 1;i < n;i++){
        int a, b, c;
        a = read(), b = read(), c = read();
        g[a].push_back({b, c});
        g[b].push_back({a, c});
    }
    dfs(root, -1);
    /*
    for (int i = 1;i <= n;i++){
        cout << dp[i] << " ";
    }
    cout << endl;
    */
    cout << dp[root];
    
    return 0;
}