今日正月十二，天转阴。

总结

今天正月十二咯。今天没有模拟赛。今天是复习。话说，今天也就是周三了，不管做什么，都会过去，如梦幻泡影。

准备先复习一下 LCT。找几道没有做过的模版题试试。

QTREE5 - Query on a tree V

洛谷上的一道题，还挺有趣的。维护虚子树和实子树的信息即可。

终于过了，调得我好难受啊，本来以为很容易的。这里注意几个点。我用 multiset 维护，但是 access 的时候有些值是会变的，要用一些变量临时存一下的。这里要注意，access 无论什么情况都不要提前更新爹的内容，谨记！

接下来复习一下 KM 算法，找到了一篇很好的博客，里面有很多例题：匈牙利与 KM 算法 。

奔小康赚大钱

KM 板子。

CF1107F Vasya and Endless Credits

题意就是每天早上向银行借钱，贷款，从这天起每天晚上就要开始还钱。有种贷款方案，每天最多贷一次。然后你要找到某一天中午买车跑出国，问这辆车最大价值。考虑把天数倒过来想，会更容易。容易发现一个二分图最大权匹配，从天数来匹配，然后每次加进去一个点就算一次，取就行。这是 KM 的方法，但是我看到其他人的代码有更加惊世骇俗的方法，按照每天还钱的数额从大到小排序，然后按着这个顺序 dp 就行了。只不过如果中间遇到就算还完贷款还能赚的情况（什么银行，我想要），就可以选择不计天数，直接扔到最后面（再次注意我们天数是反过来了的）。仔细想想，似乎的确很有道理。假设选择了一个集合，我们先去掉那些天都还完了的，剩下的肯定排在最前面按照从大到校，还完的扔到后面就行。米奇妙妙屋啊。

所以这道题本质上是能过，大概是出题人没有想到。

P6061 [加油武汉] 疫情调查

归纳一下就是，一个简单有向图，然后呢每个点再加上个自环进去，要把这个图给分成几个环的形式。边权和最小。也就是每个点入度出度都是 1。那么类似于最小链覆盖建一个满的二分图，然后边权取负跑 km 就行。左边一列就是出度，右边一列就是入度，一定能构成环。

好，接下来说一下 KM 需要的注意事项。特别是在最后一个放进队列的那个操作，要注意放的是左边的点不是右边的。可能的后果就是在的时候成环，造成 TLE。

发现还没有复习计算几何，呜

后记

明天模拟赛，加油！