「Summary」2022-06-28 做题记录

没有动机？

2022-06-28

$\mathbb{CF1391E}$

link

$dfs$ 树构造保命; 卡常题去死

注意到两个问之间的包含关系；对于构造出第二问中的给定要求，所选的一对点在同一深度；
给个证明：

对于所选出来的两对点，若是同层节点，则没有边相连；若是不同层，则只会最多两条返祖边。

关于卡常，去死吧。

$\mathbb{CF1103C}$

link

$dfs$ 树构造保命; $\mathcal{The \ degree \ of \ vertex \ is \ meaningful.}$

树上找环类问题，还是考虑返祖边。
明确说了每个结点的度至少为 $3$ ，那么对于每个叶子结点，至少有两条返祖边可以成环，此时，叶子结点至少包含在 $3$ 个不同的环上。
记叶子结点为 $u$ , 两个返祖边所的祖先结点为 $x$, $y$, 则这 $3$ 个环的环长分别为 $dep_u - dep_x + 1$, $dep_u - dep_y + 1$, $dep_y - dep_x + 2$ 。
可以论证这三个环中总有一个是 $3$ 的倍数。

$\mathbb{CF1521E}$

link

没啥好说的，就硬构造