今天做了6道题，还可以，剩下的基本是一点都不会了，太难了，等我理解再深刻一点再回来做一下吧
今天有几道题是完全靠自己想出来的了，挺好
一会把前几天的专题再补一下
昨天的做题的讲题彻底打醒了我，我什么都不是，我照我需要达到的高度差远了
我来这里不就是为了这个的吗
既然经受了大幅度的跃进，就要跟上这个提升自己的机会
明天模拟赛不管怎样一定要尽力
闲言少叙，总结下今天的题
树上问题
其实这个数据范围应该是1e5，强制nlogn，luogu有加强版
树链剖分优化dp板子题，先看看我们要干什么：查询三点两两等距的个数，很明显的树上dp
暴力思路：
f u i ： u子树内距u子树dis为i数
g u i ：u子树内两深度相同点lca与u距dis-i种类数
显然枚举边 u-v时可以n的转移 总n方
其实还有一种暴力
枚举根节点作为lca，f，g，t分别维护距lca距离i的情况数
依然暴力转移 但是空间是一维 可以过没加强数据的版本呢
正解思路：
我们考虑对于暴力1优化
先优化空间：发现dp数组的转移有很多整体移位 所以用指针（动态数组）均摊下空间 同时方便转移
再优化时间：dp很明显在维护链上问题，而且还有深度维，这种情况首选长链剖分，直接用树剖记一下dis，重儿子o1，轻儿子on，直接变身nlogn
最小异或和生成树
参考了题解的一个很巧妙的维护方式 因为是完全图 点权无序 直接sort一下
这样做有什么好处呢 在维护01trie时，就可以直接把所有权值扔到trie里，然后拥有多颗子数的点恰好为n-1（因为一次分子树代表两个数分开） 直接dfs扫过去然后对每个lca查询子树异或和
太妙了，好题，好做法
P9058 离谱的ynoi
做的糊里糊涂，如果以后回顾的话这题在第一位
思路很清晰，暴力可以枚举点对，然后神奇的支配点对思想，对于范围大距离还大的一定不会产生贡献了，这个时候剪枝就行了，手段就是点分
然后离线下来扫描线跑过就行了
其实以前是1e5强制在线的分块来着
题意给的一眼难尽 形式化：找到最少种颜色，使得这些颜色的点联通部分上没有其他颜色
帮我理解点分的一道题
贪心性质：如果以某种颜色为根跑出一个结果，再次涉及这个颜色的一定不会更优
因此可以直接点分，以根节点的颜色找，维护一个队列数数，然后把根节点子树全都断开，在每个子树上单独研究
完事了，但是我重构了3次才理解
CF632F很有东西，但是不算太难的一道题，就喜欢这种题
这个题首先是用条件1，2得到其实这是一个临界矩阵
然后条件3其实就是最小生成树
说起来轻飘飘，但是这道题的转化很有参考意义，得揣测一切限制条件的隐含意义
还有一WC2018通道 就不贴了，用随机化过的不太好意思，不过考场上一定要想尽办法拿分，这个题有极大随机成功概率的特殊性质，那就冲
正解是建虚树然后点分，极其毒瘤，以后回顾时候再看吧
更新一道题CF704C
BLACK WIDOW
23：57也是D5日报（
其实难度本身不高，主要是细节太多
这题我理解了，但是大晚上调题实在没有力气了，所以抄了一些题解的细节，原谅我
首先可以把每个式子抽象成一个点 利用xi和-xi最多出现2次的特点，把有xi与xi，xi与-xi相连，正好维护异或值的特性
建好图之后呢，考虑假设已知每个连通块对应的0情况数和1情况数，很显然可以用乘法计算答案
所以在每个连通块上考虑
显然，这种方式连出来的连通块要么是链要么是环，环就拆一条边可以转译为链的思想，对于一个链，直接dp维护要求的0，1情况数，挨个点考虑就行
完事，睡觉
就是这些
从昨天精神内耗就有些严重，感觉自己好废，但是早点意识到这里是好的
到这里就是为了承认自己的弱小，并且不是口头上那种，然后尽快找到方向提高
很有可能提高效果在这半个月的模拟赛丝毫不会显现
既然如此多做题，好好听课就行了，就算是看的题解，也是学会了一个思路，质变总会来到的
除了安慰自己，还有提醒：
-
预习
-
复习
-
补基础
不废话了.