2019-8-2

未分类

T1

KMP 模板题。

T2

考虑每条新加入的边对答案的贡献。发现新多出的答案就是与原有的边的不同的交点数+1那么 $n^2$ 枚举就行了。

然而我因为没判重爆零惹。。

T3

失智了。。。考场连这种sb题都没切

考虑一个贪心策略。每次找到未被覆盖的最深的点，将其第 $k$ 个祖先进行操作。因为当前找到了最深的点，所以以 $k$ 代祖先为根的子树内的点都会被覆盖，而越往上显然会对越多的点造成影响，所以是对的。