企业官网建设流程全解析

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

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

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

【题目来源】

洛谷：P13019 [GESP202506 八级] 树上旅行

【题目描述】

给定一棵有n nn个结点的有根树，结点依次以1 , 2 , … , n 1,2,\dots,n1,2,…,n编号，其中根结点的编号为1 11。

小 A 计划在这棵有根树上进行q qq次旅行。在第i ii次旅行中，小 A 首先选定结点s i s_isi​作为起点，并移动若干次。移动分为以下两种：

1. 移动至当前结点的父结点。特殊地，如果当前位于根结点，则不进行移动。
2. 移动至当前结点的所有子结点中编号最小的结点。特殊地，如果当前位于叶子结点，则不进行移动。

由于移动次数可能很大，对于第i ii次旅行，旅行中的移动以k i k_iki​个不为零的整数构成的序列a i , 1 , a i , 2 , … , a i , k i a_{i,1}, a_{i,2}, \dots, a_{i,k_i}ai,1​,ai,2​,…,ai,ki​​表示。对a i , j a_{i,j}ai,j​，若a i , j > 0 a_{i,j} > 0ai,j​>0则代表进行a i , j a_{i,j}ai,j​次第一种移动；若a i , j < 0 a_{i,j} < 0ai,j​<0则代表进行− a i , j -a_{i,j}−ai,j​次第二种移动。根据给出的序列从左至右完成所有移动后，小 A 所在的结点即是旅行的终点。

给定每次旅行的起点与移动序列，请你求出旅行终点的结点编号。

【输入】

第一行，两个正整数n , q n, qn,q，分别表示有根树的结点数量，以及旅行次数。

第二行，n − 1 n-1n−1个整数p 2 , p 3 , … , p n p_2, p_3, \dots, p_np2​,p3​,…,pn​，其中p i p_ipi​表示结点i ii的父结点编号。

接下来2 q 2q2q行中的第2 i − 1 2i-12i−1行（1 ≤ i ≤ q 1 \leq i \leq q1≤i≤q）包含两个正整数s i , k i s_i, k_isi​,ki​，分别表示第i ii次旅行的起点编号，以及移动序列的长度。第2 i 2i2i行包含k i k_iki​个整数a i , 1 , a i , 2 , … , a i , k i a_{i,1}, a_{i,2}, \dots, a_{i,k_i}ai,1​,ai,2​,…,ai,ki​​，表示移动序列。

【输出】

输出共q qq行，第i ii行包含一个整数，表示第i ii次旅行终点的结点编号。

【输入样例】

5 4 1 1 2 2 3 3 1 -1 -1 2 5 1 -1 1 -1 1 5 8 1 1 1 -1 -1 -1 -1 -1 5 3 -1 -1 1

【输出样例】

4 1 4 2

【核心思想】

1. 问题分析：给定一棵以1 11为根的有根树，进行q qq次旅行。每次旅行从节点s i s_isi​出发，按序列执行移动：正数a aa表示向上走a aa步（到父节点），负数a aa表示向下走∣ a ∣ |a|∣a∣步（每次到最小编号子节点）。求每次旅行的终点。由于单次移动步数可能极大，需要加速跳跃。

2. 算法选择：

   • 倍增法（Binary Lifting）：预处理每个节点向上2 i 2^i2i级祖先fa [ u ] [ i ] \text{fa}[u][i]fa[u][i]和向下连续走2 i 2^i2i次最小编号子节点son [ u ] [ i ] \text{son}[u][i]son[u][i]，通过二进制拆分将O ( a ) O(a)O(a)的线性移动优化为O ( log ⁡ a ) O(\log a)O(loga)

3. 关键步骤：

   • 建图与初始化：读取父节点数组，构建邻接表g [ u ] g[u]g[u]存储子节点，根节点父节点设为自己
   • DFS预处理倍增表：
     • 向上表：fa [ u ] [ i ] = fa [ fa [ u ] [ i − 1 ] ] [ i − 1 ] \text{fa}[u][i] = \text{fa}[\text{fa}[u][i-1]][i-1]fa[u][i]=fa[fa[u][i−1]][i−1]，即u uu的2 i 2^i2i级祖先等于其2 i − 1 2^{i-1}2i−1级祖先的2 i − 1 2^{i-1}2i−1级祖先
     • 最小编号子节点：遍历子节点时维护son [ u ] [ 0 ] \text{son}[u][0]son[u][0]为编号最小的直接子节点
     • 向下表：son [ u ] [ i ] = son [ son [ u ] [ i − 1 ] ] [ i − 1 ] \text{son}[u][i] = \text{son}[\text{son}[u][i-1]][i-1]son[u][i]=son[son[u][i−1]][i−1]，即连续向下走2 i 2^i2i步等于先走2 i − 1 2^{i-1}2i−1步再走2 i − 1 2^{i-1}2i−1步
   • 二进制拆分移动：
     • moveup ( u , a ) \text{moveup}(u, a)moveup(u,a)：遍历a aa的每一位，若第i ii位为1 11，则u = fa [ u ] [ i ] u = \text{fa}[u][i]u=fa[u][i]
     • movedown ( u , a ) \text{movedown}(u, a)movedown(u,a)：同理使用son \text{son}son表加速向下跳跃
   • 处理查询：对每个移动指令，根据正负调用对应函数，更新当前节点s ss，最终输出终点

4. 时间/空间复杂度：

   • 预处理时间复杂度：O ( n log ⁡ n ) O(n \log n)O(nlogn)，每个节点处理log ⁡ n \log nlogn层倍增
   • 单次查询时间复杂度：O ( k log ⁡ a max ⁡ ) O(k \log a_{\max})O(klogamax​)，k kk为指令数，每次移动O ( log ⁡ a ) O(\log a)O(loga)
   • 空间复杂度：O ( n log ⁡ n ) O(n \log n)O(nlogn)，两个倍增表各n × log ⁡ n n \times \log nn×logn

5. 倍增法加速树路径的核心思想：

   • 二进制拆分任意步数：将任意整数a aa拆分为2 i 2^i2i的和，通过预处理的2 i 2^i2i步跳跃表，将线性遍历转化为对数级跳跃
   • 向上与向下的对称处理：向上走父节点链和向下走固定策略（最小编号子节点）均可倍增，区别在于向下表依赖"策略一致性"（每次必须走最小编号子节点）
   • 根节点自环处理：fa [ 1 ] [ 0 ] = 1 \text{fa}[1][0] = 1fa[1][0]=1确保向上走到根后不再移动，避免越界
   • 离线预处理优势：先一次性O ( n log ⁡ n ) O(n \log n)O(nlogn)预处理，之后每次查询O ( log ⁡ a ) O(\log a)O(loga)，适合大量查询场景
   • 适用于树上快速跳跃、LCA、路径查询、大规模步数移动问题

【算法标签】

#普及+ #倍增

【代码详解】

#include<bits/stdc++.h>usingnamespacestd;constintN=100005;// 定义最大节点数常量N为100005intn,q;// n为节点数，q为旅行次数intp[N];// p[i]表示节点i的父节点编号（未使用，用fa数组替代）intfa[N][21],son[N][21];// fa[u][i]表示u的2^i级祖先；son[u][i]表示u连续走2^i次"最小编号子节点"到达的节点vector<int>g[N];// 邻接表，g[u]存储u的所有子节点voiddfs(intu)// 深度优先搜索，预处理每个节点的倍增祖先表和最小编号子节点倍增表{// 预处理向上倍增表：fa[u][i]表示u向上走2^i步到达的祖先for(inti=1;i<=20;i++)// 枚举倍增层次，2^20约100万，足够覆盖N=1e5fa[u][i]=fa[fa[u][i-1]][i-1];// u的2^i级祖先 = u的2^(i-1)级祖先的2^(i-1)级祖先son[u][0]=u;// son[u][0]初始化为u自身，用于比较找最小编号子节点for(autov:g[u])// 遍历u的所有子节点v{dfs(v);// 递归处理子节点v// 更新u的最小编号子节点：如果当前还没有子节点，或者v的编号更小if(son[u][0]==u||v<son[u][0]){son[u][0]=v;// son[u][0]记录u的最小编号直接子节点}}// 预处理向下倍增表：son[u][i]表示从u连续走2^i次"最小编号子节点"到达的节点for(inti=1;i<=20;i++)// 枚举倍增层次son[u][i]=son[son[u][i-1]][i-1];// 连续走2^i次 = 先走2^(i-1)次，再走2^(i-1)次}intmoveup(intu,inta)// 二进制拆分向上移动：从u向上移动a步（走到父节点），使用倍增加速{for(inti=0;i<=20;i++)// 枚举每一位二进制if((a>>i)&1)// 如果a的第i位为1，表示需要向上走2^i步u=fa[u][i];// u跳到其2^i级祖先returnu;// 返回向上移动a步后的节点}intmovedown(intu,inta)// 二进制拆分向下移动：从u向下移动a步（每次走到最小编号子节点），使用倍增加速{for(inti=0;i<=20;i++)// 枚举每一位二进制if((a>>i)&1)// 如果a的第i位为1，表示需要向下走2^i步u=son[u][i];// u跳到连续走2^i次最小编号子节点后的位置returnu;// 返回向下移动a步后的节点}intmain(){cin>>n>>q;// 读入节点数n和旅行次数qfor(inti=2;i<=n;i++)// 循环读入节点2到n的父节点信息{cin>>fa[i][0];// 读入节点i的父节点fa[i][0]g[fa[i][0]].push_back(i);// 将i加入父节点的子节点列表}fa[1][0]=1;// 根节点1的父节点设为自己（向上走到根就停止）dfs(1);// 从根节点开始DFS预处理倍增表while(q--)// 循环处理q次旅行{ints,k,a;// s为起点，k为移动序列长度，a为每次移动的步数cin>>s>>k;// 读入起点s和序列长度kwhile(k--)// 循环处理序列中的k个移动指令{cin>>a;// 读入当前移动指令aif(a>0)// 如果a为正数，表示向上移动a步（走到父节点）s=moveup(s,a);// 从s向上移动a步else// 如果a为负数，表示向下移动|a|步（走到最小编号子节点）s=movedown(s,-a);// 从s向下移动-a步}cout<<s<<endl;// 输出第i次旅行的终点编号}return0;}

【运行结果】

5 4 1 1 2 2 3 3 1 -1 -1 4 2 5 1 -1 1 -1 1 1 5 8 1 1 1 -1 -1 -1 -1 -1 4 5 3 -1 -1 1 2