[[点分树]] [[树的重心]] [[最小生成树]] [[树链剖分]]

前情提要

题目链接

今天考的还行吧，有三道题都不是很难。

题解

T1

这道题 impossible 很好判。
这道题我最开始是想用高斯消元的。后来手算了一下，发现不能解出准确解。后来灵光一闪，根据题目里说到可能为 0 的边，想到了树，发现只要子树给它满足就刚好能平衡。切了。

T2

第二道题其实也很好想。看到数据范围我就知道是枚举纵列然后搞横排。

由于我怕横排 lower_bound 会超时，然后就去搞双指针。结果后来大样例下来的时候一堆细节。

蚌埠住了。

标程都是二分的。蚌埠住了。二分还很好写。痛失40分。

T3

这道题看了一眼不会做，第二眼不会做。再一看，这暴力分好香啊。然后把暴力切了，70。

正解没怎么看懂，但是看了邓老师（大头鱼）的方法，倒是几经周折理解了。

用点分治，在点分树上跳。不过要注意一些细节。

改题也基本上是很快过，没有调试多久，没有写出一些弱智还劳神的错误，但是要注意一些细节。

说明我的代码能力还是提高了一点点的。(‾◡◝)

T4

考场上将正解想出来了，震惊。

就是最小生成树，两种情况，判一判。

就是基环树上的环上面把链上最大的那个边权求一求搞一搞。

这道题我联想到了之前在 S 城的一道题：[[题解/绍兴一中 2023/7.1 测试#T4|7.1 测试]]

最开始求链上最大值我是暴力往 lca 上跳的，后来怕超时，写了个树剖。

结果……和那天的一样，直接暴力跳找答案都不会超时……

涨知识了（可能一般这种都不会刻意去卡吧哈哈，也有可能一个图最小生成树以外的边每条都在链上跑一次的平均复杂度不高吧）

后记

继续努力！