AtCoder Grand Contest 009
C
先写出暴力的dp，然后发现可行的转移构成一个区间，前缀和差分优化一下（略）
D
就是把它弄成一棵高度尽量小的点分树。假设 \(i\) 在点分树内的深度为 \(d_i\)。观察 \(d\) 的性质：若 \(d_x=d_y\)，那么至少有一个 \(z\in path(x,y)\) 满足 \(d_z
（为什么满足这个性质就一定可以构建出点分树呢？我不知道）
考虑把这个性质对应到点分树的每个子树里，就是
1、若 \(x\) 的两个不同的儿子子树中都出现了 \(k\) 且它们中间没有 \(
2、若 \(x\) 子树中出现 \(k\)，并且它们之间的 \(d\) 都 \(\ge k\)。则 \(d_x\ne k\)。
根据这个就可以在书上贪心了。如果是构建一棵重心点分树，答案不超过 \(\log n\)，所以 \(d_x\) 只有 \(\log n\) 种取值。那么可以直接用一个二进制串 \(f_x\) 表示 \(subtree(x)\) 中出现了哪些数值。暴力枚举每一位或者用 \(builtin\) 函数可以做到 \(O(n)-O(n\log n)\)
E
不说具体的。
把这个过程放到 \(k\) 叉树上，共 \(n+m\) 个叶子，设每个叶子的节点为 \(d_i\)，那么权值为 \(1\) 的叶子 \(i\) 会对结果产生 \(k^{-d_i}\) 的贡献。由此可以想到把结果写成 \(k\) 进制小数 \(p=0.c_1c_2c_3\dots=\sum k^{-d_i}[a_i=1]\)，再考虑进位，得到关于 \(c\) 的限制条件。根据 \(1-p\) 还可以得到类似的限制。然后进行数位dp，前缀和优化一下。
原文：https://www.cnblogs.com/whx666/p/agc009.html