P10109 [GESP202312 六级] 工作沟通

题意理解

公司是一棵有根树，根为0号老板。每个员工，他自己、父亲、祖父……一直到根，全部是他的管理者。
每次查询给出一批参会员工，找出编号最大的一个结点，这个结点必须是所有参会员工的共同管理者（即该点出现在每一个参会员工向上追溯到根的路径上）。

等价题意：求多个点的公共祖先，取编号最大的公共祖先。

数据范围：N ≤ 300，Q ≤ 100。数据规模很小，可以直接暴力，不需要LCA倍增。

思路1：暴力统计公共祖先

  1. 存储每个点的直接上级 f[i]。

  2. 对于一组查询：

    • 开计数数组cnt[]。
    • 对每一个参会员工，向上递归遍历他全部祖先（包含自己），每遇到一个祖先，cnt[祖先] +=1。
    • 如果某个点cnt[x] == m（m为本场参会总人数），说明这个点是全部参会人员的公共祖先。
    • 编号从大到小遍历，第一个满足cnt[x]==m就是答案（题目要求编号最大）。
原理：只要x是y的管理者，y往上走一定会经过x。每一个参会人走过的祖先计数+1；只有全部m个人都走过的结点，计数才会等于m。

思路2：反向建图（存下属）

  • 常规：f[i]保存i的父亲（领导）
  • 反向建图：vector<int> son[]，son[fa].push_back(i)，存每个领导的全部直接下属。
    son[x]里面存的就是x的直接手下；从x出发DFS，可以访问x管理的全部所有人（x的整棵子树）。

流程：

  1. 读入每个员工i的领导fa，执行 son[fa].push_back(i)，构建下属邻接表。

  2. 处理每组查询：

    1. 保存本场参会人员集合。
    2. 员工编号从大到小枚举候选主持人x（一旦找到合法直接返回，满足编号最大）。
    3. 从x出发DFS遍历，标记x能够管理到的全部人（x子树全部结点）。
    4. 判断：所有参会的人，是否全部都被标记。
    5. 如果全部参会人员都被标记：x就是答案，直接输出。
核心逻辑：x可以管理y ⇔ y在x的子树里面。
题目要求：x可以管理全部参会人员 ⇔ 所有参会点都属于x的子树。
从大到小枚举x，第一个合法的就是编号最大解。

P11375 [GESP202412 六级] 树上游走

题意

完全二叉树，根1；i左儿子2i，右儿子2i+1，父节点i/2。
U向上、L向左子、R向右子。
$n\le 10^6$，中间运算直接乘法会溢出long long，题目仅保证最终结果≤1e12。

思路：延迟操作（延迟下放）

  1. 设置变量t：当前实际节点编号；s延迟计数器，记录暂时不执行的向下(L/R)步数。阈值1e12。

  2. 遇到 L/R：

    • 向下计算之后不超过1e12，直接执行乘法更新t。
    • 向下运算会超过阈值，不做乘法，s++，把这步向下操作寄存。

  3. 遇到 U：

    • 如果t=1，根节点，无法向上，跳过。
    • 如果s>0：优先消耗寄存的向下操作，s--，抵消本次向上，t不变。
    • 如果s=0：没有寄存操作，真实向上，t /= 2。
  4. 题目保证最终结果合法，处理完全部指令后s一定为0，直接输出t。
核心坑点：先向下很多步会数值溢出，不去真实乘2，用计数器记账；后续向上U可以直接抵消记账的向下，避免大数溢出。

P11962 [GESP202503 六级] 树上漫步 题解

题意

一棵树，从点 i 出发走偶数步（可以重复走点、来回走边），问最终可以到达多少个不同结点。 n ≤ 2×10^5。

思路：树二分染色（奇偶层）

画个树简单分析一下，容易发现，奇数层的点通过偶数步可以走到所有其余奇数层的点，偶数层也是同理。

树是二分图，可以黑白二染色，把结点分成两类：距离根为偶数层 even、奇数层 odd。

树上两点 u，v，两点之间路径真实距离为 dis。
如果允许来回绕路：可以在边上往返，每往返一次步数 +2，不改变终点。

能以偶数步从 u 走到 v 等价于：u与v的奇偶类别相同。

统计整棵树偶数层结点总数 cnt0，奇数层结点总数 cnt1。

  • 若起点 i 属于偶层：答案就是 cnt0
  • 若起点 i 属于奇层：答案就是 cnt1

核心原理：来回走边可以任意加2步，只看起点终点奇偶性是否一致，和路径长短无关。只需要一次 DFS/BFS 求出整棵树奇偶点数量，不需要对每个点单独搜索。

P14076 [GESP202509 六级] 货物运输 题解

题意

n座城市构成一棵树，根是1号首都。车队从首都出发，需要走过全部城市，城市允许重复访问，终点不用回到首都。求路线总道路长度的最小值。
n <= 10^5。

思路

  1. 树上遍历，如果走完所有点并且最后返回起点：每条边都要走进去再退回来，所有边总长度乘以2。总和 = 全部边长度之和 * 2。
  2. 题目不需要回到首都，我们可以决定最后一条到叶节点的路径，这一条路径只走一遍，不用折返。
  3. 想要整体总路程最小，就要让省去不走折返的那一条路径尽可能长，也就是求：从根1出发的最长路径（树的根到最远点距离，根的最长深度）。
  4. 答案 = 所有边总长度 * 2 − 根节点出发的最长路径长度。

核心原理：
普通树遍历要往返，每条边走两次；终点停在最远叶子，这条最长路径就只需要走单程，省下这一段往返的路程。

样例1：
全部边总和 = 6+1+5 =12，总和*2 =24。
从1出发最长路径：1‑3‑4，长度 1+5=6。
24‑6 =18，和样例输出18一致。

样例2：
所有边总和*2 =12；根最长路径=3；12‑3=9，匹配输出9。

实现要点：一次读边累加全部边总和；DFS/BFS求出从根1出发的最大距离；做减法输出结果。

P10722 [GESP202406 六级] 二叉树 题解

题意

给定一棵n个节点二叉树，每个节点有初始颜色0或者1。q次操作，每次选定一个节点，把该节点的整棵子树所有节点颜色翻转。输出全部操作完成之后每个节点颜色。
n,q <= 10^5。

思路：树上懒标记（传递翻转标记）

  1. 翻转偶数次等价等于没有翻转，奇数次等价翻转1次。先统计每个节点被直接操作的次数，只保存0或者1。
  2. DFS遍历整棵树，把父节点的翻转状态向下传递给子节点。
  3. 当前节点最终是否翻转 = 当前节点自身标记 ^ 父节点传下来的翻转标记，一转以不转则转，同时不转或同时转都等同于不转。
  4. 如果本点最终需要翻转，就把节点颜色取反；并把本次实际翻转状态传给自己的孩子。
  5. 不要每次操作暴力遍历子树，暴力会超时。

核心原理：
子树翻转，标记打在根节点；遍历的时候向下传递标记。异或逻辑：翻转两次抵消。不用修改子树每一个点，遍历的时候再计算实际效果。

样例1：
初始串100101；三次操作1、3、2。
统计各点打标记：节点1标记1，节点3标记1，节点2标记1。
DFS向下传递标记，逐点算出最终颜色，输出010000。

实现要点：
二叉树存左右孩子；标记只有0/1；dfs参数传递父节点实际翻转状态；最后输出颜色。

P13016 [GESP202506 六级] 最大因数

题意

树结点编号 $1\sim10^9$，根是1。
结点 $k(k\ge2)$ 的父结点：k除去自身以外最大的因数。
q次询问，求两点 $x,y$ 的树上距离（边的条数）。

树上距离公式：
$$dist(x,y)=depth(x)+depth(y)-2\cdot depth(lca(x,y))$$
代码实现是树上求LCA的暴力上跳模板。

fa(n)父结点函数

  • 可以找n的最小质因子i，找到直接返回n/i，比找最大质因子来的快。

depth(n)深度函数

从n不断向上跳父结点直到根1，统计跳的次数（边数）。

  • depth(1)=0；
    例：4→2→1，depth(4)=2；8→4→2→1，depth(8)=3。

查询求距离流程（暴力LCA上跳）

  1. 算出 $dx=depth(x),\ dy=depth(y)$，ans初始0
  2. 深度大的点向上跳，跳到和另一个点深度相同，每跳一次ans+1
  3. 如果此时x==y，直接ans就是答案。
  4. x、y一起同步向上跳，直到x等于y（找到LCA），每一轮两点各跳一步，ans +=2。
  5. 输出ans。

样例1：
1和3：depth(1)=0，depth(3)=1；y往上跳一步到1，ans=1，输出1。
2和5：depth(2)=1，depth(5)=1；x=2,y=5不同；同步上跳 x=1,y=1，ans +=2 →ans=2。
4和8：depth(4)=2，depth(8)=3；8向上跳一次变成4，ans=1，此时x==y，输出1。

60%部分分思路

(x,y)≤1000，可以预处理fa数组、depth数组打表，查询直接查表；数字到1e9不能打表，必须实时计算fa。

P14919 [GESP202512 六级] 路径覆盖

题意

一棵根为1的树，所有结点初始白色。
要求：每一个叶子到根的路径上，至少存在一个黑色结点。
把结点i染黑代价c[i]，求总代价最小。

含义：切断所有叶子通往根的路径；选若干点染色，每条叶子到根路径至少命中一个黑点，求最小总花费。

DP状态与转移

dfs(u)：处理以u为根的子树，满足子树内全部叶子条件的最小代价。

两种决策：

  1. 把u点染黑：子树全部叶子路径已经被u截断，子树内部不用再选任何点，代价就是 c[u]。
  2. u不染色：那么u的每一棵子树必须各自满足条件，所有子树答案累加 sum(dfs(v))，v是u的儿子。

转移：
dfs(u) = min( c[u], 所有儿子v的dfs(v)相加 )

边界：叶子结点（没有孩子）
此时不能什么都不选，这条路径必须在此处选点，只能染自己：
dfs(u) = c[u]

算法流程

  1. 读入父数组，建树，children[u]存u的全部儿子；
  2. dfs后序遍历；叶子直接返回c[u]；
  3. 非叶子：返回「染当前点代价」和「所有子树代价求和」二者较小值；
  4. dfs(1)就是全局答案。

40%部分分思路 n≤16

暴力枚举子集，枚举哪些点染黑；然后遍历每一片叶子，检查叶子到根路径是否存在黑点，两个DFS套着写，没办法的办法。

P15801 [GESP202603 六级] 完全二叉树

题意

对树上每一个结点作为子树根，统计有多少棵子树为完全二叉树。

思路1：DFS

判定原理：
把待判定子树映射为数组式完全二叉树虚拟编号：根p=1，左孩子p 2，右孩子p 2+1。对完全二叉树来说，假设总共x个点，则第x个点的存储编号正好是x，因为是1、2、3、4挨个按顺序存的。

  • c：子树实际结点个数
  • mp：遍历过程出现的最大虚拟编号
    完全二叉树条件：虚拟编号从1连续无空洞，mp == c。

深度截断作用：
完全二叉树深度上限为 log2(n)+2；递归时深度一旦超过该值，直接标记子树非法并返回。

执行步骤：

  1. 读入n，存储每个点左右孩子 l[i],r[i]。
  2. 循环每一个root(1~n)作为子树根。
  3. 重置 c=0，mp=0，f=0；执行dfs(root,虚拟编号1，深度1)。
  4. dfs中遇到真实结点更新c、mp；深度超限置f=1直接返回。
  5. 如果 mp == c && f==0，答案+1。

思路2：BFS层序判定

判定核心规则：层序遍历子树，空结点0允许出现；一旦碰到空结点，后续不允许再有真实结点；空之后出现真实结点 → 不是完全二叉树。

注意：空结点0必须入队列，不能跳过。

执行步骤：

  1. 枚举每一个root作为子树根。
  2. 队列初始放入root，标记meet_null=false。

  3. 取出队头：

    • 如果是0，meet_null置true。
    • 如果是真实结点：若meet_null已经为true，直接判定该子树不合法；否则把它的左右孩子（允许0）入队。

  4. 队列为空遍历结束，没有提前return false，则该子树合法，ans++。

    // l[], r[] 全局，0代表没有孩子
bool isComplete(int root)
{
 queue<int> q;
 q.push(root);
 bool meet_null = false;
 while (!q.empty())
 {
     int u = q.front();
     q.pop();
     if (u == 0)
     {
         meet_null = true; // 遇到空节点了
     }
     else
     {
         if (meet_null) // 非空节点之前有空节点
             return false;
         q.push(l[u]);
         q.push(r[u]);
     }
 }
 return true;
}

P17013 [GESP202606 六级] 满二叉树

题意

对树上每一个结点作为子树根，统计有多少棵子树为满二叉树。

满二叉树两个硬性条件：

  1. 不存在单儿子结点，非叶子结点必须同时拥有左、右两个儿子；
  2. 子树内所有叶子结点的相对深度完全相同。
合法满二叉树性质：结点总数为 $n$，满二叉树最大高度为 $\log_2 n$，子树深度超过该值一定不是满二叉树，可以直接剪枝判错。

思路1：枚举根 + DFS + 深度剪枝

判定原理：
枚举每一个root作为子树根，DFS遍历当前子树做校验。

  • 遍历过程发现结点只有左儿子或者只有右儿子，子树直接非法。
  • 记录子树所有叶子的相对深度，全部叶子深度必须保持一致。
  • 递归深度超过 $\log_2 n$，直接标记非法并且return，不再向下递归。

执行步骤：

  1. 读入n，存储每个点左右孩子 l[i],r[i]。
  2. 循环每一个root(1~n)作为子树根。
  3. 重置标记、叶子深度记录；执行dfs(root,相对深度0)。
  4. dfs过程检测单儿子、统一叶子深度、深度超限剪枝。
  5. 遍历完成无违规，答案+1。

复杂度：每个子树DFS最多向下递归 $\log n$ 层，总时间复杂度 $O(n\log n)$。

思路2：后序DFS

每个结点u保存两组信息

  • ok[u]：bool，u的子树是否为满二叉树
  • h[u]：若为满二叉树，代表子树内叶子的相对深度，无意义则忽略

转移：

  1. u是叶子结点(l[u]==0 && r[u]==0)：ok[u]=true，h[u]=0
  2. u只有左儿子 或者 只有右儿子：ok[u]=false

  3. u左右儿子都存在：

    • 左子树或者右子树不是满二叉树，ok[u]=false
    • 左右都是满二叉树，但h[l[u]] != h[r[u]]，ok[u]=false
    • 否则 ok[u]=true，h[u] = h[l[u]] + 1

执行步骤：

  1. 读入数据建树；
  2. 后序遍历，自底向上算出ok与h；
  3. 统计ok[u]等于true的结点总数即为答案。

易错点

  1. 满二叉树不等于完全二叉树，满二叉树不允许出现单儿子。
  2. 深度剪枝必须写return终止递归，否则退化为 $O(n^2)$。
  3. 深度为子树内部相对深度，不是整棵大树的绝对深度。
  4. n=1e5递归链式树会栈溢出，可改为迭代后序。

标签: none

评论已关闭