昨天 vp：ICPC2022 Nanjing。
K 题比较弱智，但是后面摆了，懒得写。
本来录屏了，后来感觉打的不太行就删掉了。
160 E Color the Tree
很难的啊！没想到大家都会做。
可以发现不同层的结点互不干扰，我们不妨枚举每一层，把每一层的答案加和。
我们建出第 \(d\) 层结点对应虚树，只需 dp 当前子树所有叶子被染色的最小代价，这个很好处理。
复杂度 \(O(n\log n)\)，当然也可以线性。
161 F Triangles
MO 题为啥要出 ACM 里来。
一个很好的策略是连接某个锐角三角形三边中点，这样锐角三角形数量会加三。
可以证明 \(n\leqslant 7\) 无解，我们只需构造出 \(n=8,9,10\) 的解。
162 H Factories Once More
其实比较简单，只是之前有一道类似的正睿题没做出来比较丢人，所以记录一下。
dp 每棵子树选多少个结点的最大权值，一条边的经过次数就是较深子树中选定点数量。
列出转移方程，它是先做一个二次函数加，然后闵可夫斯基和。归纳证明 dp 数组是上凸的，维护差分值，只需支持等差数列加，以及启发式合并，使用 splay 启发式合并即可 \(O(n\log n)\)。
163 J Perfect Matching
不难，不过有意思。
观察可知 \(|a_i-a_j|=|i-j|\) 等价于 \(a_i+i=a_j+j\) 或者 \(a_i-i=a_j-j\)。
建立二分图，左边代表 \(a_i+i\) 右边代表 \(a_i-i\)，原序列一个下标对应一条边。
那么无非就是构造无向图图相邻边的匹配，这个的结论是每个连通块边数为偶数就有解，构造随便 dfs 树一下就好了。
164 L Proposition Composition
WC 刚讲过！
165 APC001 H Generalized Insertion Sort
标签：结点,20,log,29,2023,锐角三角,dp From： https://www.cnblogs.com/xiaoziyao/p/17062541.html