2024“钉耙编程”中国大学生算法设计超级联赛（6）

Problems	AC
7494. 造花（简单版）	○
7495. 造花（困难版）	⊕
7496. 飞车狂飙	○
7497. 不醒人室	○
7498. 交通管控	⊕
7499. 解方程	格基归约，弃疗
7500. 树上 MEX 问题	⊕
7501. 树形 DNA	待补
7502. 数字加减	大模拟，弃疗
7503. Rikka 与子集 IV	多项式，弃疗
7504. 天天爱跑步	待补

1001 造花（简单版）

1007 树上 MEX 问题

MEX，数数

给定一棵 n 个点的树，每个点有点权，点权是 0 到 n - 1 的排列，求所有连通块(连通导出子图)的 MEX 之和。

$1 \le n \le 10^5$

好题，学到了

直接的统计答案是 枚举 i，对 i * 恰好 mex = i 的子图数量 求和。这样的话答案是很难算的。

众所周知在这类问题上有个常见的 trick 是在 钦定 和 恰好之间转换。

假如我们钦定[0, i - 1] 这 i 个点选的话，剩下随意，那么 mex 只能是 >= i 的。这个数量我们其实是更方便求一点的。

换言之，假设我们求出了 mex >= i 的子图数量 $num_i$ 。那么恰好 mex = i 的子图数量就是 $num_i - num_{i + 1}$

$$
ans = \sum_{i = 1}^{n}{i \times (num_i - num_{i + 1})}
= \sum_{i = 1}^{n}{i \times num_i} - \sum_{i = 2}^{n + 1}{(i - 1) \times num_i}
= num_1 + \sum_{i = 2}^{n}{num_i} - n \times num_{n + 1}
= \sum_{i = 1}^{n}{num_i}
$$

接下来考虑如何计数 $num_i$。

跑一个 $dp_u = \prod_{v \in son(u)} (dp_v + 1)$ 表示 u 这个点必选，u 和 u 的子树能构成的联通子图数量。

将 0 作为树的 rt。那么 [0, i] 这些点以及路径上的其他点都是必选的，我们把这看成一个集合 S。剩下的点都是可选可不选。$num_i$ 就等于所有和 S 这坨东西直接相连且不在 S 里面的点的 (dp_v + 1) 的乘积

那么在 S 集合新加进来一个点的时候，只需要不断往上跳，大力维护：原来是可选可不选的 (dp_v + 1)，现在是必须要选的 (dp_v)。

因为每个点最多只会被加入到 S 一次，所以是对的。

1011 天天爱跑步

基环树

给一棵基环树，对每个点 i 求过 i 的最长简单路径。

$1 \le n \le 10^5$

假如不是基环树，是一棵树，那么答案是好求的，一个点无非是两条往下或者一条往下一条往上的拼起来，这个东西是很好 dp 的。

如果是基环树，一个环挂着很多树。一个点 i 往下走的最长路径是 $mxd_i$，那么每个 i 就是要找个 j 配对，构成一个 $mxd_i + mxd_j + 环上路径$