本文分享的必刷题目是从蓝桥云课、洛谷、AcWing等知名刷题平台精心挑选而来，并结合各平台提供的算法标签和难度等级进行了系统分类。题目涵盖了从基础到进阶的多种算法和数据结构，旨在为不同阶段的编程学习者提供一条清晰、平稳的学习提升路径。

欢迎大家订阅我的专栏：算法题解：C++与Python实现！

附上汇总贴：算法竞赛备考冲刺必刷题（C++） | 汇总

【题目来源】

洛谷：P14919 [GESP202512 六级] 路径覆盖 - 洛谷

【题目描述】

给定一棵有 $n$ 结点的有根树 $T$，结点依次以 $1,2,\dots ,n$ 编号，根结点编号为 $1$。方便起见，编号为 $i$ 的结点称为结点 $i$。

初始时 $T$ 中的结点均为白色。你需要将 $T$ 中的若干个结点染为黑色，使得所有叶子到根的路径上至少有一个黑色结点。将结点 $i$ 染为黑色需要代价 $c_i$，你需要在满足以上条件的情况下，最小化染色代价之和。

叶子是指 $T$ 中没有子结点的结点。

【输入】

第一行，一个正整数 $n$，表示结点数量。

第二行，$n-1$ 个正整数 $f_2,f_3,\dots ,f_n$，其中 $f_i$ 表示结点 $i$ 的父结点的编号，保证 $f_i<i$。

第三行，$n$ 个正整数 $c_1,c_2,\dots ,c_n$，其中 $c_i$ 表示将结点 $i$ 染为黑色所需的代价。

【输出】

一行，一个整数，表示在满足所有叶子到根的路径上至少有一个黑色结点的前提下，染色代价之和的最小值。

【输入样例】

4
1 2 3
5 6 2 3

【输出样例】

2

【算法标签】

#普及

【代码详解】

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

#define int long long
const int N = 100005;
int n;  // 节点总数
int w[N];  // 存储每个节点的权值
int x;  // 临时变量，用于输入父节点编号
vector<int> a[N];  // 邻接表，存储树的结构，a[u]存储节点u的所有子节点

// 深度优先搜索函数
// 参数u：当前处理的节点
void dfs(int u)
{
    // 如果当前节点是叶子节点（没有子节点），直接返回
    if (a[u].empty())
    {
        return;
    }
    
    int sum = 0;  // 存储所有子节点权值的总和
    
    // 遍历当前节点的所有子节点
    for (int i = 0; i < a[u].size(); i++)
    {
        // 递归处理子节点
        dfs(a[u][i]);
        
        // 累加子节点的权值
        sum += w[a[u][i]];
    }
    
    // 更新当前节点的权值：取自身权值和子节点权值总和的较小值
    w[u] = min(w[u], sum);
}

signed main()
{
    cin >> n;  // 输入节点总数
    
    // 输入树的边关系，构建树结构
    for (int i = 2; i <= n; i++)  // 从第2个节点开始，第1个节点是根节点
    {
        cin >> x;  // 输入节点i的父节点编号
        a[x].push_back(i);  // 将节点i添加到其父节点x的子节点列表中
    }
    
    // 输入每个节点的初始权值
    for (int i = 1; i <= n; i++)
    {
        cin >> w[i];
    }
    
    // 从根节点1开始进行深度优先搜索
    dfs(1);
    
    // 输出根节点的最终权值
    cout << w[1] << endl;
    
    return 0;  // 程序正常结束
}

【运行结果】

4
1 2 3
5 6 2 3
2

转载自CSDN-专业IT技术社区

原文链接：https://blog.csdn.net/guolianggsta/article/details/160985153