2024“钉耙编程”中国大学生算法设计超级联赛（3）
HDU 逆天系统，赛时显示的不是过题队伍数量而是 AC 数。有个队最后 1h 狂交 1003。
| Problems | AC |
|---|---|
| 7457 深度自同构 | ○ |
| 7458 旅行 | ⊕ |
| 7459 游走 | 待补 |
| 7460 游戏 | |
| 7461 数论 | |
| 7462 字符串 | |
| 7463 单峰数列 | ○ |
| 7464 比特跳跃 | ○ |
| 7465 圣芙蕾雅 | |
| 7466 绘世之卷 | |
| 7467 抓拍 | ○ |
| 7468 死亡之组 | ○ |
1001 深度自同构 DP
对于由若干有根树构成的森林，定义该森林是深度自同构的，当且仅当森林中任意两个深度相同的节点都有相同的度。
请计数有多少个深度自同构的无编号有根树森林，使得其恰好由 n 个节点构成，答案对 998244353 取模。
我们先考虑 由 n 个节点的合法的树的个数。转化一下条件，任意深度相同的节点有相同的度数，这其实意味着深度相同节点的子树形态是完全一样的。（度数其实是对树的形态的限制）
这个东西是可以递推的，令 $f_i$ 表示有 i 个点的合法的树的个数。拿出一个点作为根节点，剩下 $n - 1$ 个点我们枚举因数转移 $f_i=\sum_{d \mid(i-1)} f_d$。
那么对于森林的个数，其实就类似了，只不过不用多拿出一个点来作为根节点。$ans_i=\sum_{d \mid i} f_d$
1002 旅行 线段树合并
本题要求树上一些不相交的链使得权值和最大，每个链要求起始点和 终止点颜色相同，权值为起点和终点的权值和。
第一场刚学了个树上的 DSU on Tree / 线段树合并 这类的问题，赛时尝试过往这方面去想，还是不会，正好多学学。
先来波感性理解，假如我们在树上 DP，我们在 LCA 处枚举经过这个点的链。如果这个点不被经过的话，就是把所有孩子节点的 dp 值加起来；如果被 (u, v) 经过的话，我们就要 (u, v) 的贡献以及 u 下面子树的贡献，v 下面子树的贡献，和这条链上其他点的其他孩子的 dp 值。
那么我们令 颜色 作为线段树的下标，维护 dp 值的 max。
dp[u][0] 存不经过的值，dp[u][1] 则是算上了经过的值
先遍历一遍子树，算出 dp[u][0]。然后遍历儿子，把每个儿子的线段树减去 dp[v][1] 后 merge，在 merge 的时候，如果递归到了叶子节点，就维护 dp[u][1]。
1007 单峰数列 线段树
典题。可以直接线段树大力维护。事实上，维护差分数组可以更简单。
1008 比特跳跃 建图
给你一张图 和 k。点 x 可以花 k * (x or y) 的代价跳到点 y。求点 1 到各个点的最短路。
1011 抓拍 三分
原题，弱化版。
1012 死亡之组
签到。
2024“钉耙编程”中国大学生算法设计超级联赛（3）