本文分享的必刷题目是从蓝桥云课、洛谷、AcWing等知名刷题平台精心挑选而来，并结合各平台提供的算法标签和难度等级进行了系统分类。题目涵盖了从基础到进阶的多种算法和数据结构，旨在为不同阶段的编程学习者提供一条清晰、平稳的学习提升路径。
欢迎大家订阅我的专栏：算法题解：C++与Python实现！
附上汇总贴：算法竞赛备考冲刺必刷题（C++） | 汇总
【题目来源】
洛谷：P9304 「DTOI-5」3-1 - 洛谷
【题目描述】
里克在视线可及的范围内发现了一颗古老的「神树」。
神树是一颗树，树上有n nn个含有魔法装置的位置。经过初步「考察」，有n − 1 n - 1n−1条魔法连接，第i ( 1 ≤ i ≤ n − 1 ) i(1 \leq i \leq n - 1)i(1≤i≤n−1)条连接u i , v i u_i, v_iui,vi两个魔法装置，保证u i ≠ v i u_i \neq v_iui=vi且1 ≤ u i , v i ≤ n 1\leq u_i,v_i\leq n1≤ui,vi≤n。这两个装置可以相互双向地在1 11单位时间内通行，保证仅由这n − 1 n - 1n−1条连接，每个魔法装置都可以相互到达。
此外，有n − 1 n - 1n−1条特殊连接，对于每个魔法装置i ∈ [ 2 , n ] i \in [2, n]i∈[2,n]，可以瞬间传送到第1 11个魔法装置，花费0 00单位时间。特殊连接总共只能使用一次。
里克初始在魔法装置1 11处。现在，给出这棵「神树」的结构，里克想要在若干时间内研究尽可能多的魔法装置。我们假定，研究一个魔法装置只需要到达该装置处，并且不需要花费额外时间。
里克想让你尽快计算出，对所有k ∈ [ 1 , n ] k \in [1, n]k∈[1,n]，如果要恰好研究k kk个不同的魔法装置，并且随之返回魔法装置1 \bm 11，最少应花费多少时间。
【输入】
第一行，一个整数n nn。
接下来n − 1 n - 1n−1行，每行两个整数u i , v i u_i, v_iui,vi。
【输出】
共n nn行，第i ii行一个整数表示k = i k = ik=i的答案。
【输入样例】
5 1 2 1 3 2 4 2 5【输出样例】
0 1 2 4 6【算法标签】
《洛谷 P9304 「DTOI-5」3-1》 #树形数据结构# #深度优先搜索DFS# #树的遍历# #O2优化#
【代码详解】
#include<bits/stdc++.h>usingnamespacestd;constintN=100005,M=N*2;// 定义常量，N: 最大节点数，M: 最大边数(无向图)intn,u,v,dep[N],maxx,ans;// n: 节点数, dep: 深度数组, maxx: 最大深度, ans: 答案inth[N],e[M],ne[M],idx;// 邻接表存储树// 添加无向边voidadd(inta,intb){e[idx]=b,ne[idx]=h[a],h[a]=idx++;// 添加边a->b}// DFS计算节点深度voiddfs(intu,intfa)// u: 当前节点, fa: 父节点{if(fa)// 如果不是根节点{dep[u]=dep[fa]+1;// 当前节点深度 = 父节点深度 + 1maxx=max(maxx,dep[u]);// 更新最大深度}for(inti=h[u];i!=-1;i=ne[i])// 遍历当前节点的所有邻接点{intj=e[i];// 邻接节点jif(j==fa)continue;// 如果是父节点，跳过dfs(j,u);// 递归遍历子节点}}intmain(){memset(h,-1,sizeof(h));// 初始化邻接表cin>>n;// 输入节点数// 输入n-1条边，构建树for(inti=1;i<n;i++){cin>>u>>v;add(u,v),add(v,u);// 添加无向边}// 从节点1开始DFS，计算每个节点的深度和树的最大深度dfs(1,0);// 对于每个可能的i值，计算答案for(inti=1;i<=n;i++){ans=2*(i-1)-min((i-1),maxx);cout<<ans<<endl;}return0;}【运行结果】
5 1 2 1 3 2 4 2 5 0 1 2 4 6
