本文分享的必刷题目是从蓝桥云课、洛谷、AcWing等知名刷题平台精心挑选而来并结合各平台提供的算法标签和难度等级进行了系统分类。题目涵盖了从基础到进阶的多种算法和数据结构旨在为不同阶段的编程学习者提供一条清晰、平稳的学习提升路径。欢迎大家订阅我的专栏算法题解C与Python实现附上汇总贴算法竞赛备考冲刺必刷题C | 汇总【题目来源】洛谷P10113 [GESP202312 八级] 大量的工作沟通【题目描述】某公司有N NN名员工编号从0 00至N − 1 N-1N−1。其中除了0 00号员工是老板其余每名员工都有一个直接领导。我们假设编号为i ii的员工的直接领导是f i f_ifi。该公司有严格的管理制度每位员工只能受到本人或直接领导或间接领导的管理。具体来说规定员工x xx可以管理员工y yy当且仅当x y xyxy或x f y xf_yxfy或x xx可以管理f y f_yfy。特别地0 00号员工老板只能自我管理无法由其他任何员工管理。现在有一些同事要开展合作他们希望找到一位同事来主持这场合作这位同事必须能够管理参与合作的所有同事。如果有多名满足这一条件的员工他们希望找到编号最大的员工。你能帮帮他们吗【输入】第一行一个整数N NN表示员工的数量。第二行N − 1 N-1N−1个用空格隔开的正整数依次为f 1 , f 2 , … f N − 1 f_1, f_2, \dots f_{N-1}f1,f2,…fN−1。第三行一个整数Q QQ表示共有Q QQ场合作需要安排。接下来Q QQ行每行描述一场合作开头是一个整数m mm2 ≤ m ≤ N 2 \leq m \leq N2≤m≤N表示参与本次合作的员工数量接着是m mm个整数依次表示参与本次合作的员工编号保证编号合法且不重复。保证公司结构合法即不存在任意一名员工其本人是自己的直接或间接领导。【输出】输出Q QQ行每行一个整数依次为每场合作的主持人选。【输入样例】5 0 0 2 2 3 2 3 4 3 2 3 4 2 1 4【输出样例】2 2 0【核心思想】问题分析给定一棵以 0 号员工为根的有根树每个员工可以管理其所有后代包括自己。对于多组询问每组给出若干员工编号需要找到一个编号最大的员工使得该员工是所有这些员工的共同祖先即能管理所有参与者。若存在多个取编号最大者。由于祖先关系具有传递性共同祖先即所有节点的最近公共祖先LCA及其祖先。因此问题转化为求一组节点的 LCA最近公共祖先。在从根到该 LCA 的路径上找出编号最大的节点。由于编号不随深度单调不能简单取 LCA 本身的编号需要预处理根到每个节点的路径最大编号。算法选择倍增法求 LCA预处理每个节点的倍增祖先表f[u][k]2 k 2^k2k级祖先和深度dep[u]同时预处理mx[u]表示从根节点到节点u的路径上所有节点编号的最大值。查询过程对每组询问依次将每个参与节点与当前 LCA 合并求 LCAlca getLCA(lca, x)最终得到所有参与节点的 LCAt。答案即为mx[t]因为所有能够管理这些节点的员工正是从根到t路径上的所有节点编号最大者即为该路径最大值。关键步骤读入与建树读取N NN对于i 1 … N − 1 i1 \dots N-1i1…N−1读取f_i在树中添加边(f_i, i)。DFS 预处理从根节点 0 开始 DFS计算每个节点的深度dep[u]、倍增祖先f[u][k]k 0..20 k0..20k0..20以及路径最大编号mx[u] max(mx[parent], u)。LCA 函数使用倍增法求两个节点的最近公共祖先。处理询问对于每组询问读取m和第一个节点将其作为初始 LCA然后依次读取剩余节点不断更新 LCA。最终输出mx[lca]。时间/空间复杂度预处理O ( N log N ) O(N \log N)O(NlogN)。每次询问O ( m log N ) O(m \log N)O(mlogN)总复杂度可接受N , Q ≤ 10 5 N, Q \le 10^5N,Q≤105。空间复杂度O ( N log N ) O(N \log N)O(NlogN)。树上祖先与路径最大值管理关系的树形结构员工之间的管理关系构成一棵树祖先即管理关系。任意一组员工的共同管理者即为它们的公共祖先。最近公共祖先LCA所有公共祖先中深度最大的节点是 LCA它是管理这些员工所需的最低管理者所有能管理这些员工的节点是从根到 LCA 路径上的所有节点。路径最大值预处理由于节点编号不随深度单调需预先计算根到每个节点的路径最大编号以便快速回答“路径上最大编号”的查询。适用场景适用于树形结构中的“最近公共祖先”查询及“路径信息统计”问题特别适合需要多次查询多节点共同祖先的场景。【算法标签】#普及 #最近公共祖先【代码详解】#includebits/stdc.husingnamespacestd;constintN100005;// 最大员工数量intn,q;// n: 员工总数, q: 合作场次intf[N][25];// f[u][i]: u 的 2^i 级祖先根节点 0 的祖先为 0intdep[N];// dep[u]: u 在树中的深度根节点深度为 0intmx[N];// mx[u]: 从根节点到 u 的路径上最大的节点编号vectorintg[N];// 邻接表存储树无向边// 深度优先搜索预处理每个节点的深度、倍增祖先以及路径最大编号voiddfs(intu,intfa){f[u][0]fa;// 直接父节点dep[u]dep[fa]1;// 深度 父节点深度 1mx[u]max(mx[fa],u);// 路径上最大编号 max(父路径最大, 当前节点)// 倍增祖先预处理for(inti1;i20;i)// 2^20 1e5足够覆盖 N{f[u][i]f[f[u][i-1]][i-1];// u 的 2^i 级祖先}// 递归遍历子节点for(intv:g[u]){if(vfa)continue;// 跳过父节点dfs(v,u);}}// 倍增法求最近公共祖先 (LCA)intlca(intu,intv){// 确保 u 的深度不小于 v使 u 位于较深位置if(dep[u]dep[v])swap(u,v);// 将 u 提升到与 v 同一深度for(inti20;i0;i--){if(dep[f[u][i]]dep[v])continue;// 若跳 2^i 步后深度小于 v则跳过该步uf[u][i];// 向上跳 2^i 步}if(uv)returnu;// v 是 u 的祖先// 同时提升 u 和 v直到它们的父节点相同for(inti20;i0;i--){if(f[u][i]f[v][i])continue;// 若跳 2^i 步后相遇则跳过该步避免越界uf[u][i];vf[v][i];}returnf[u][0];// 返回父节点即为 LCA}intmain(){cinn;// 输入员工总数// 读入每个员工的直接领导编号 1 到 n-1for(inti1;in;i){intx;cinx;f[i][0]x;// 记录直接父节点g[x].push_back(i);// 建无向边g[i].push_back(x);}// 从根节点 0 开始预处理dfs(0,0);cinq;// 输入合作场次while(q--){intm;cinm;// 参与本次合作的员工数// 读取前两个员工编号用于初始化 LCAinta,b;cinab;inttlca(a,b);// 当前参与者的 LCA// 依次与剩余员工合并 LCAfor(inti3;im;i){intx;cinx;tlca(t,x);// 更新所有参与者的共同祖先}// 能够管理所有参与者的节点为 t 的所有祖先包括 t// 其中编号最大的节点即为 mx[t]根到 t 路径上的最大编号coutmx[t]endl;}return0;}【运行结果】5 0 0 2 2 3 2 3 4 2 3 2 3 4 2 2 1 4 0