2019年二月刷题列表

Preface

虽然二月剩下没多少了，但是为了勉强保持格式还是写一写吧

这个月的首要目标就是在剩下的时间里让这个月的做题数争取达到\(50\)，不过感觉希望渺茫啊

初三中考百天倒计时要来了，所以为此我多获得了\(30\)分钟的晚自习（=去机房），还是很爽的

省选的知识点陆陆续续地差不多都过了一遍了，但是很多掌握的还是不够，最近继续主写LCT和多项式吧，还有雅礼集训的题目也是很好的

2-20

今天早上报到，然后下了大雨坐公交就堵车迟到，几乎全身湿透。。。

期初考的三场感觉还好，像我这种寒假作业几乎未动的人都能勉强胡一个

晚上想都没想就去机房了，先开两道LCT：

• Luogu P3703 [SDOI2017]树点涂色 这个染色的操作就是一个access的过程嘛！那么我们直接用splay维护所有颜色相同的链即可。2操作就是一个树上差分，那么既然要用到LCA了就顺带树剖一下得了，3操作就是子树最大值，DFS序上用线段树维护即可，每次access断边的时候修改即可。
• SP16549 QTREE6 - Query on a tree VI 这个系列的题之前一直都是用点分/边分写的，这次见到一道LCT神题。首先容易想到对两种颜色单独开LCT，这样询问就是子树大小。但是这样修改时遇到菊花图就跪了，所以可以用一个套路：化点为边，我们把点的颜色给父边，然后每次只改一条边即可。注意这里由于树的形态固定，所以我们要写不换根的LCT来维护父子关系。

然后写一个基环树的题，发现这个东西一直不是很策的来：

• Luogu P4381 [IOI2008]Island 仔细观察题目其实就是一个基环树森林求直径和的形式。我们关于环分类讨论，首先把不经过环的答案（就是子树内的直径）用树形DP求出来，然后记下环上每个点向子树内延伸的最长链，在环上选两个点找到最大答案即可。这个可以容易用单调队列优化到\(O(n)\)。

2019年二月刷题列表

原文：https://www.cnblogs.com/cjjsb/p/10414360.html