这是我写的第8个正式题解 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 【A75466】[GESP202409 七级] 小杨寻宝 题目链接 点这里 题目大意 有一棵 nnn 个节点，n−1n-1n−1 条边的树 可以任意选择起点并在树上移动 但是：只能经过每条边 111 次（也就是说必须要走简单路径） 树上有一些节点被放置了宝物，如果到达这些节点，将会获得这个宝物 问：能否取得所有宝物 解题思路 1. 算法选择 dfs+bfs 2.1. 核心思路 * dfs+记忆化 构造一个新的数组dis，数组的每一个节点代表树上相对应节点的子树中有多少个宝藏 * 根据dis数组枚举 找到根节点 * bfs 对每个节点做判断（如果其同时拥有 222 条以上的宝藏分支，则整体不合法，能全部遍历完则合法） 2.2. 具体、详细的思路 > dfs+记忆化 * dfs(u, fa)，代表当前节点为u,其父节点为fa * 定义数组，disidis_idisi 的值表示树上编号为 iii 的节点的子树中有的宝藏数量 * 如果这个点已经算过了，直接返回答案 * 设置一个cnt变量，代表子树中拥有的宝藏数量。将cnt初始值设为 aua_uau * 遍历当前节点连接的所有邻居节点 * * 如果当前节点为父节点，则跳过 * * 否则调用 dfs(当前节点，u)dfs(当前节点，u)dfs(当前节点，u) * 返回最终答案 * * 因为我们用的是记忆化的思路，所以应该 return dis[u] = cnt > find_root()函数找根节点 因为我们要知道，根节点不一定是 111 ，所以需要一个单独的函数找根节点（否则就需要另一个思路） * 循环u从 1∼n1 \sim n1∼n * 设置一个cnt变量，记录当前节点 iii 有多少个相邻节点是 disi>0dis_i > 0disi >0 的 * * 因为合法路径一定是一条链，所有宝物都在这条链上，所以链的端点一定满足：最多只有 1 个方向存在宝物。 * * 如果当前节点 iii 对应的 disi>0dis_i > 0disi >0，表示当前节点有 111 个方向存在宝物 * 如果 cnt<2cnt <2cnt<2 说明符合链端点条件，选为根 * * 如果当前节点为父节点，则跳过 * * 否则调用 dfs(当前节点，u)dfs(当前节点，u)dfs(当前节点，u) * 返回根节点值，若最终无返回则默认节点 111 为根节点 > bfs * 建立队列，储存 (当前节点, 父节点)，防止无向树反向走 * 起点（根节点）入队，标记已访问 * 循环取出队首节点 uuu、它的父节点 fafafa * 设置一个变量has，记录队首节点子树有多少宝藏分支 * 遍历 uuu 所有相邻点 nownownow： * * 如果 nownownow 是父节点，直接跳过，禁止走回头路 * * 如果 nownownow 的子树有宝藏，宝藏分支计数器 cnt+1cnt + 1cnt+1 * 没访问过的点，先打标记、再入队，继续遍历 * 对当前点做判断： * * 同时拥有 2 条及以上宝藏分支，直接判定整体不合法，返回 falsefalsefalse * * 全部点遍历完毕无违规，返回 truetruetrue 3. 复杂度分析 * 时间复杂度：O(tn)O(tn)O(tn) * 空间复杂度：O(n)O(n)O(n) 易错点/坑点 1. 循环输入边数范围是：1∼n−11 \sim n - 11∼n−1 2. 树存储时为无向树 AC 代码

题目等价于要判断是否存在一条最长的链，使得所有宝物都在这条链上 发现题目是一棵树，而树上找一条链的走法是相对唯一的。根据题目要求，我们从树的“一端”走起，如果遇到一个点它的父亲和>=2个叶子都有宝物，那么肯定不行，因为走到叶子后回不来了 进一步抽象，发现只要图中出现下面这个模型那么就无法走到所有宝藏：（假设每个o都代表某个子树） o-o-o .... | ....o 判断标准：有一个节点有大于等于三条边都直接或间接地连接到了有宝物的节点，那么就无法得到所有宝物 考虑统计出某个结点x，以x为根节点的子树所包含的宝物数量为f[x]，以x的子节点为根的子树中有宝物的子树数量为s[x] * 如果s[x]>=3显然不合法 * 如果s[x]>=2，且在其父亲方向存在宝藏（如果 总宝藏数-f[x]>0），那么不合法 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 大神解法： 题目显然等价于问所有宝箱是否在一条链上。 稍微转化一下题意，即我们现在要找到一条链，使得这条链上有宝物的节点数量尽可能多。 想到这里我们发现这个和树的直径比较相似，那么我们直接大胆将深度定义为从根到这个节点上有宝箱节点的数量，然后做一遍树的直径。最后判断直径长度是否等于所有有宝箱节点的数量即可。 做完以后我们发现这道题过了，其实证明也很简单。我们考虑把价值转到边上，即对于所有有宝箱的节点，让它所连的所有边长度都加上一。因为如果一条路径经过这条边，那么它一定也经过这个点，所以这样给边赋权后跑树的直径是对的，即上述思路正确。