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 的子图数量 $nu{m}_i$ 。那么恰好 mex = i 的子图数量就是 $nu{m}_i-nu{m}_{i+1}$

$$ans=\sum _{i=1}^{n}i\times (nu{m}_i-nu{m}_{i+1})=\sum _{i=1}^{n}i\times nu{m}_i-\sum _{i=2}^{n+1}(i-1)\times nu{m}_i=nu{m}_1+\sum _{i=2}^{n}nu{m}_i-n\times nu{m}_{n+1}=\sum _{i=1}^{n}nu{m}_i$$

接下来考虑如何计数 $nu{m}_i$。

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

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

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

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

1011 天天爱跑步

基环树

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

$1\le n\le {10}^5$

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

如果是基环树，一个环挂着很多树。一个点 i 往下走的最长路径是 $mx{d}_i$，那么每个 i 就是要找个 j 配对，构成一个 $mx{d}_i+mx{d}_j+\mathrm{环}\mathrm{上}\mathrm{路}\mathrm{径}$