20231004 NOIP#15总结
时间安排
7:40~8:00
看题，\(A,B\) 会第一档爆搜，别的不会。
8:00~9:30
写完 \(A,B\) 的爆搜。
9:30~11:00
会了 \(C\) 的暴力还加了点优化，一下写了 \(1.5h\)，不过有点难写。（我是真没想到连个菊花图都没有直接 \(AC\) 了
11:00~11:40
\(D\) 能看出是线段树但一点不会写，于是罚坐。
总结反思
实话说 \(T3\) 就差一点就是正解了为什么不多想一下。
题解
A.DP
设 \(f[i][j]\) 表示考虑 \(i\) 个数构成深度 \(\leq j\) 的树的形态有多少个。
然后枚举目前序列最大的数在序列中的位置为 \(k\) 则有：（就是 \(k\) 为根，随意选 \(k-1\) 个构造左子树，其余构造右子树）
B.DP
满足 \(\forall i\geq 2,i^2\nmid\)所选数的乘积，即乘积质因数拆分为 \(p_1^{e_1}p_2^{e_2}\cdots p_m^{e_m}\) 后 \(\max\{e_1,e_2,\cdots,e_m\}=1\)。
而在 \(1\sim n\) 中的数 \(\geq \sqrt n\) 的质因数最多只会有一个。所以使用根号分治，将 \(\sqrt n\) 以下的质因子状压处理即可。
C.树上倍增
考虑小日 \((x)\) 和小月 \((y)\) 肯定会互相对着走，在最中间的点 \((rt)\) 相遇。这时，如果路径长度是奇数，则 \(x\) 后手，否则先手。那么统计答案是就是以 \(rt\) 为根时所有子树去掉 \(x\) 和 \(y\) 的两棵之外其它第奇数（或偶数）大的权值和。
那么可以将这个看做是以 \(rt\) 为根是所有子树大小排序后序列的奇数（或偶数）个值之和，而遇到 \(x\) 或 \(y\) 所在的子树时则翻转奇偶性。
那么可以预处理出对于每个点分奇偶性统计以当前点为根时子树的权值前缀和即可做 \(O(1)\) 查询。