本文分享的必刷题目是从蓝桥云课、洛谷、AcWing等知名刷题平台精心挑选而来，并结合各平台提供的算法标签和难度等级进行了系统分类。题目涵盖了从基础到进阶的多种算法和数据结构，旨在为不同阶段的编程学习者提供一条清晰、平稳的学习提升路径。
欢迎大家订阅我的专栏：算法题解：C++与Python实现！
附上汇总贴：算法竞赛备考冲刺必刷题（C++） | 汇总
【题目来源】
洛谷：[P2052 NOI2011] 道路修建 - 洛谷
【题目描述】
在 W 星球上有n nn个国家。为了各自国家的经济发展，他们决定在各个国家之间建设双向道路使得国家之间连通。但是每个国家的国王都很吝啬，他们只愿意修建恰好n − 1 n - 1n−1条双向道路。
每条道路的修建都要付出一定的费用，这个费用等于道路长度乘以道路两端 的国家个数之差的绝对值。例如，在下图中，虚线所示道路两端分别有2 22个、4 44个国家，如果该道路长度为1 11，则费用为1 × ∣ 2 − 4 ∣ = 2 1×|2 - 4|=21×∣2−4∣=2。图中圆圈里的数字表示国家的编号。
由于国家的数量十分庞大，道路的建造方案有很多种，同时每种方案的修建费用难以用人工计算，国王们决定找人设计一个软件，对于给定的建造方案，计算出所需要的费用。请你帮助国王们设计一个这样的软件。
【输入】
输入的第一行包含一个整数n nn，表示 W 星球上的国家的数量，国家从1 11到n nn编号。
接下来n − 1 n - 1n−1行描述道路建设情况，其中第i ii行包含三个整数a i a_iai，b i b_ibi和c i c_ici，表示第i ii条双向道路修建在a i a_iai与b i b_ibi两个国家之间，长度为c i c_ici。
【输出】
输出一个整数，表示修建所有道路所需要的总费用。
【输入样例】
6 1 2 1 1 3 1 1 4 2 6 3 1 5 2 1【输出样例】
20【算法标签】
《洛谷 P2052 道路修建》 #树形数据结构# #广度优先搜索BFS# #深度优先搜索DFS# #NOI# #2011#
【代码详解】
#include<bits/stdc++.h>usingnamespacestd;#defineintlonglong// 将int定义为long long类型constintN=1000005,M=N*2;// N: 最大节点数, M: 最大边数(双向边)intn;// 节点数intcnt[N];// cnt[u]: 以u为根的子树大小intans;// 最终答案inth[N];// 邻接表头inte[M];// 边的终点intw[M];// 边的权重intne[M];// 下一条边intidx;// 边计数器// 添加边voidadd(inta,intb,intc){e[idx]=b;// 存储终点w[idx]=c;// 存储边权ne[idx]=h[a];// 插入到链表头部h[a]=idx++;// 更新头指针}// 第一次DFS：计算每个节点的子树大小voiddfs(intu,intfa){cnt[u]=1;// 初始化，包含自己// 遍历所有邻接点for(inti=h[u];i!=-1;i=ne[i]){intj=e[i];// 子节点if(j==fa)continue;// 跳过父节点dfs(j,u);// 递归处理子节点cnt[u]+=cnt[j];// 累加子树的节点数}}// 第二次DFS：计算总贡献voiddfs2(intu,intfa){// 遍历所有邻接点for(inti=h[u];i!=-1;i=ne[i]){intj=e[i];// 子节点if(j==fa)continue;// 跳过父节点// 计算边(u, j)的贡献// cnt[j]: 子树j的节点数// n - cnt[j]: 另一部分的节点数// 两部分的差值乘以边权ans+=w[i]*abs(cnt[j]-(n-cnt[j]));// 递归处理子节点dfs2(j,u);}}signedmain()// 因为使用了#define int long long，所以用signed main{// 初始化邻接表memset(h,-1,sizeof(h));// 输入节点数cin>>n;// 输入n-1条边for(inti=1;i<n;i++){intu,v,w;// 使用scanf加速输入scanf("%d%d%d",&u,&v,&w);// 添加双向边add(u,v,w);add(v,u,w);}// 第一次DFS：计算子树大小dfs(1,0);// 第二次DFS：计算总贡献dfs2(1,0);// 输出结果cout<<ans<<endl;return0;}【运行结果】
6 1 2 1 1 3 1 1 4 2 6 3 1 5 2 1 20
