总结

今天和外校一起考的，感觉他们都太厉害了。这里模一模邓老师，拿到了 rank5，差一点 AK。

今天有 4 道题，结果只会 T1，但是基本上人均 A T1。

还有，今天赛制是 IOI，很是奇怪呢。比赛链接

题解

T1

我好弱智，这道题写了两个小时。首先容易考虑到肯定是用总的减去有重的。然后我最开始考虑的是点分治，打完后发现假了。然后又想了一下，想到了换根 dp。但是由于我优秀的实现方式，我还打了一个长链剖分，然后 WA 成10分。我当时差点想摆烂。后来发现一个的 lca 在另一条链上就行，所以直接暴力把所有链搞下来然后树上前缀和就可以。

T2

很一眼的题，但是实现是真的很难啊。首先可以看出分成一个二叉树的形状，并且长度的种类很少。按长度来排序从左到右就可以，找到长度再在那里面二分。当时主要是不知道怎么求一个子树会有多少个长度的，然后折腾了半天，没搞出来。后来才发现用个 map 暴力存就行了，因为搜索也就最多 log 种长度，均摊是 log 的。注意时间复杂度。

T3

是之前的一道原题啊。虽然我一眼看出了我做过且还改出来了，但是我，忘记了。

是 [[总结/2023年9月30日模拟赛#T4|2023年9月30日模拟赛T4]] 的原题。大概又理解了一遍。看到有一种另解，就说一下。就是暴力度数的拆分，说是只有 5400 种。然后分配度数，建立二分图，跑 KM 就行（怎么又是你）。然后呢背包搞一下，和官方题解一样就行。

T4

好题好题。知识点是拟阵交。今天学习了一下。放几个博客，我自己就不说了。

入门级别，讲得很好：wsc2008的拟阵

附带一篇例题的题解：【题解】CF1556H 和一篇洛谷日报：拟阵与最优化问题 。

然后是提高版本的拟阵博客（我看不懂，就先挂在这里了）：从拟阵基础到 Shannon 开关游戏

然后先做一下 DIY Tree 。

注：这道题，写的时候 MLE 了，是清空的问题，详情请见 [[AFO 小技巧]] 的更新。

总结一下拟阵交这类题，差不多就是有两个限制，要选一些东西，达到最优。生成树是最常见的其中一种限制，另外一个限制可以是随便一个拟阵。

后记

这个题还是很好的，好评！很有趣的题目。

一周又结束啦呵呵，他们半期也考完了。一切又都像什么都没有发生过一样了。