## MEXP
#树形dp #质数 #前缀和 #差分
首先我把最小的、不整除其中一个数的最小质数转成每个数，不整除它的最小质数，中的最小值。因此对于每一个点我们维护一个值，表示不整除它的最小质数，那么 $f(x,y)$ 就变成了求 $x$ 到 $y$ 路径上的点的最小值。
由于前 $10$ 个质数的 LCM（即乘积）就已经超过值域了，因此再离散化一下变成 $0\sim 9$ 的数。发现很小，所以考虑把它放进状态里面做 dp。设 $dp_{i,j}$ 表示在 $i$ 到 $i$ 的子树中任意一个点的路径，其中最小值为 $j$ 的个数，那么合并子树时就可以枚举 $j$ 然后把儿子连到当前节点上，新的 $j$ 就是 $\min(a_x,j)$。那么统计 $i$ 到 $i$ 子树的路径答案和就很容易了。
但是还有一种路径是 $x$ 往上走若干个节点到一个祖先，然后往其它子树走。这种情况可以使用整个树和当前子树做差得到……吗？由于根是不一样的，因此 $j$ 很难处理。如果我们只往上面走一步的话，还是很好处理的，用父亲的状态整体对儿子的状态做差（按照合并时的方式逆着做），然后统计。
但是很明显可以往上走超过 $1$ 步，因此可以做一个树上前缀和。
```cpp
include <iostream>
#include <vector>
using namespace std;
using LL = long long;
const LL kMaxN = 2e5 + 5, kP = 12, kD[] = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37};
LL a[kMaxN], dp[kMaxN][kP], ans[kMaxN], tmp[kMaxN], t, n;
vector<LL> e[kMaxN];
void dfs(LL x, LL f) {
fill(begin(dp[x]), end(dp[x]), 0);
dp[x][a[x]] = 1;
for (LL i : e[x]) {
if (i == f) {
continue;
}
dfs(i, x);
for (LL j = 0; j < kP; j++) {
dp[x][min(a[x], j)] += dp[i][j];
}
}
for (LL i = 0; i < kP; i++) {
ans[x] += kD[i] * dp[x][i];
}
}
void dfs2(LL x, LL f) {
if (f) {
for (LL i = 0; i < kP; i++) {
dp[f][min(a[f], i)] -= dp[x][i];
tmp[i] = dp[x][i];
}
for (LL i = 0; i < kP; i++) {
ans[x] += dp[f][i] * kD[min(a[x], i)];
}
for (LL i = 0; i < kP; i++) {
dp[x][min(a[x], i)] += dp[f][i];
}
for (LL i = 0; i < kP; i++) {
dp[f][min(a[f], i)] += tmp[i];
}
}
for (LL i : e[x]) {
if (i == f) {
continue;
}
dfs2(i, x);
}
}
int main() {
cin.tie(0)->sync_with_stdio(0);
for (cin >> t; t; t--) {
cin >> n;
fill(e + 1, e + n + 1, vector<LL>());
fill(ans + 1, ans + n + 1, 0);
for (LL i = 1; i <= n; i++) {
cin >> a[i];
for (LL j = 0; j < kP; j++) {
if (a[i] % kD[j]) {
a[i] = j;
break;
}
}
}
for (LL i = 1, u, v; i < n; i++) {
cin >> u >> v;
e[u].push_back(v);
e[v].push_back(u);
}
dfs(1, 0);
dfs2(1, 0);
for (LL i = 1; i <= n; i++) {
cout << ans[i] << ' ';
}
cout << '\n';
}
return 0;
}
```
## 音乐节目
#数学 #组合数学 #博弈论 #博弈dp
赛时我靠着手玩样例+大脑烧烤+结论猜测，得到了 $m=1$ 下的答案为 $\cfrac{k}{2^{n-1}}$，成功获得了 $20$ 分。但没有继续思考了，遗憾挂分。赛后我把我的思路写一下。
首先刚才我只写了子任务一，但是做人是要有追求的，所以我们盯着子任务二，发现其 $\le 2000$ 的数据范围很适合做一个 $\mathcal O(nm)$ 的 dp，所以可以设计状态：设 $dp_{i,j}$ 表示为当 $n=i,j=m$ 时的答案。首先是初始状态，如果 $n=m$ 时即 Bob 每次都要加，因此答案为 $nk$，所以有 $dp_{i,i}=ik$。
然后就是我最摸不透的转移部分了，主要还是对这种博弈题“绝对聪明”的各个情况分析能力不行。假设多一个回合，新回合 Alice 选择的数为 $x$，如果 Bob 这回合要增加音量，那么值就是 $dp_{i-1,j-1}+x$，如果 Bob 这回合降低音量，那么值就是 $dp_{i-1,j}-x$，但是 Bob 会选择音量小的，因此值是 $\min(dp_{i-1,j-1}+x,dp_{i-1,j}-x)$。而 Alice 会选择最大化音量，因此最终值为 $\max\limits_{x\in[0,k]}\min(dp_{i-1,j-1}+x,dp_{i-1,j-x})$。这个值是 $dp_{i-1,j-1}+x$ 和 $dp_{i-1,j}-x$ 的平均值。
我觉得思路还是不够清晰，其实就是 Alice 虽然是先手，但是 Bob 掌控着最终决策权，因此 Alice 选完任意的之后 Bob 会选 $\min$ 值，Alice 需要最大化 $\min$ 值，也就是求 $\min$ 值的 $\max$。
所以我们得到了转移方程 $dp_{i,j}=\cfrac{dp_{i-1,j-1}+dp_{i-1,j}}{2}$。时间复杂度 $\mathcal O(nm)$。
现在我们需要优化。假设初始状态为 $(i,i)$，那么我们需要计算他有多少种方式得到 $(n,m)$，并根据步数相应地折半。把除以二拆掉，可以发现上面的形式和组合数递推公式一模一样，但是把 $(i,i)$ 作为组合数的初始状态，那么就需要进行一些减法偏移。最终会得到分子为 $\dbinom{n-i-1}{m-i}$，带上初始状态值就是 $ik\times\dbinom{n-i-1}{m-i}$。然而步数恒定是 $n-i$ 步的，因此分子为 $2^{n-i}$，最终答案就是
$
\sum_{i=1}^m ik\times\binom{n-i-1}{m-i}
$
还要注意 $n=m$ 的边界情况。
## 两个排列
不会啊，代码啥都没写。
## 蜗蜗序列
首先轻而易举地写出对于 $n\le 7$ 的数据时间复杂度为 $\mathcal O((n+1)^n 2^n n)$ 的暴力 DFS，然后观察到子任务二只有 $\le 10$，因此加上一个可行性优化之后直接把 $\le n$ 的所有答案都跑出来（最后一个开 O2 跑了两分钟），打成表之后直接输出。时间复杂度 $\mathcal O(1)$，成功通过 $30$ 分。
## 总结
总分：$100+20+0+30=150$
主要还是第二题没有仔细思考，写完第一题就开摆了，其实第二题的思路并不是过于复杂的，如果下次能更加仔细、深度地思考应该就可以在这种结论题中取得更好的结果。~~主要还是放 T2 以为做不了，放 T1 肯定能做出来。~~ 其中一个例子就是上次 [[2025.9.11 模拟赛]] 的 T1，这么难我都花 3h 写出来了。