「Summary」2022-08-16 做题记录

怎么这么久都没写题解了？！

2022-08-16

$\mathbb {1416D}$

纯 YY

像极了另外一道题，这里指 棘手的操作 ，但是不一样，一个是加边一个是删边。

其实可以转化，把删边操作看成是加边操作从后往前做，现在要解决的问题就是将图上的查询通过 dfn 序转到序列上。具体而言，从后往前考虑每个操作，如果是删边就用并查集从后往前连，在连的同时，把图建出来，如果是查询，则需要记录这个连通块的链头，和此时的连通块大小。

之后可以把 dfn 跑出来，从前往后依次回答询问就好了。

$\mathbb{HDU6430}$

线段树合并板

板题没什么好解释的，注意要先加当前点的贡献，再合并儿子。

关于时间复杂度，因子个数一定在 $\log(v)$ 的级别里，所以没有问题。

$\mathbb{HDU5452}$

结论

也不能说就是结论，看到题发现其实并不好做，在于限制了树边只能割一条。

或许可以从限制入手，只割一条树边能把一个点从树上割下来就只能是叶子，很容易地可以得到割掉叶子需要 $deg_{u}$ 次，有没有比这个更优秀的做法呢？可以论证，在只割掉一条树边的情况下，如果割除两个连在一起的点需要 $deg_v+deg_u - 1$ ，这就已经没有只割掉叶子优秀了。

$\mathbb{CF983E}$

手要废了 /kk

树上路径的题一般都可以从单链的情况出发，即考虑这道题中有一个 $u$ ，往上跳到 $pre$ 的最小步数，看起来是个比较套路的树上倍增，记 $g_{i, j}$ 表示从第 $i$ 个点出发，往上面跳 $2^j$ 步能够到达的最小深度的点。

回到这个问题，就转化成两个点 $u,v$ 往 $lca(u, v)$ 跳总共需要的最小步数，乍一看，这不跟单链一样嘛，直接码码码，写完发现过不了样例 🤡。

因为我没有分类讨论。

考虑这几种需要单独处理的情况：

• 两个点都无法跳到 $lca$ ，判 $-1$
• 分别达到 $lca$ 的最后一条路是否是一条

为啥要判这个呢？因为有可能有一条路跨过 $lca$ 连接了两个结点，那么此时两个点只要有一个跳一下就行了。

怎么判捏？这个其实就是个二位数点，主席树搞一搞就行啦。