时间安排
7:40 - 7:50
读题，毫无思路。
7:50 - 8:10
尝试写 A 题暴力，发现写不出来。
8:10 - 8:30
写了 B 题爆搜。
8:30 - 9:30
罚坐，想了一会 D 题，毫无思路。
9:30 - 10:00
读懂了 C 题，会了链的部分分，写的时候会了“正解”（随机图复杂度 \(O(n\log n)\)，菊花图复杂度 \(O(n^2)\)）。
10:00 - 11:40
决定冲 C 题，结果最后没调出来。
总结反思
1.比赛策略出现严重问题，应当把能拿的所有分都拿到后再去冲正解。
2.dp 问题没有思路，思维达不到。
题解
T1
DP,设 \(f_{i,j}\) 表示\(i\)个数中建成高度小于等于\(j\)的方案数，然后转移
\[f_{i,j}=\sum_{k=1}^j f_{k-1,\min(k-1,j-1)} * f_{i-k,\min(i-k,j-1)} * C_{i-1}^{k-1} \]T2
观察到\(\sqrt{500}\) 小于 23，也就是每个数最多有一个质因子大于等于 23，于是就可以根号分治后 DP。
T3
树上倍增，然后用前缀和优化。
T4
单侧递归线段树，可类比 洛谷P4198。
标签：10,00,23,复杂度,30,50,05 From： https://www.cnblogs.com/cannotdp/p/17743753.html