CF1778F - 树形DP

 前 言 

好久不更了，随便发一篇，证明我还活着，也还没彻底退役。

---

CF1778F - Maximizing Root

 题 意 

给定一棵 $n$ 个节点的有根树， $1$ 号节点为根，每个点有点权 $a_i$ ， 可以执行至多 $k$ 次如下操作，求最终 $a_1$ 的最大值。

一次操作为，选择一个没被选过的节点 \(u\) ，以及一个整数 \(x\) ，要求 \(x\) 是以 \(u\) 为根的子树内所有点权的公因数；然后将这个子树内所有点权乘以 \(x\) 。

多测。 \(2 \le n \le 10^5\) , \(\sum n \le 2 \times 10^5\) ; \(0 \le k \le n\) ;   \(\forall i, 1 \le a_i \le 1000\) .

 题 解 

由于每个点只能用一次，不难想到最优解一定是自底向上操作，且最后一步一定操作 $1$ 号点。显然是树形 DP ，根据数据范围排除一切 $O(nk)$ 的思路，又发现每次操作只选 $a_1$ 的因数作为 $x$ 一定能产生最优解（这是因为最后一次操作只能选 $a_1$ 的因数作为 $x$ ，中间过程的 $x$ 的非 $a_1$ 因数部分在最后用不上），而 $1000$ 只有 $32$ 个因数；于是往 $O(n \cdot 32)$ 思考。

下文中 \(I\)、\(J\) 分别表示 \(a_1\) 的第 \(i\)、\(j\) 个因数（从小到大）。

借助树形 DP 的经典套路“含根/不含根”，令 \(f_{u, i}\) 表示： \(u\) 的所有后代点权全为 \(I\) 的倍数所需的最小操作次数，\(g_{u, i}\) 表示： \(u\) 的整个子树点权全为 \(I\) 的倍数所需的最小操作次数；无方案则为 \(INF\) 。显然 \(f_{u, i}\) 的条件即 \(u\) 的任意儿子 \(v\) 都满足 \(g_{v, i}\) 的条件，于是有：

\[ f_{u, i} = \sum_{v \in son(u)} g_{v, i} \]

如果 \(I\) 已经是 \(a_u\) 的因子，那么 \(f_{u, i}\) 条件成立即 \(g_{u, i}\) 条件成立，初始化 \(g_{u, i} = f_{u, i}\) ；否则初始化 \(g_{u, i} = INF\) 。

接下来考虑整棵子树乘上一个公因子 \(x\) ，使得 \(a_u\) 具有因子 \(I\) 。既然已经有 \(a_u = x \times (a_u / x)\) 即 \(I \nmid [x \times (a_u / x)]\) 了，那么因子 \(I\) 的产生一定不是 \(a_u / x\) 这个不变部分产生的，也就是必有 \(I | x^2\) 。也就是说，选一个 \(J \ne I\) 且 \(I \mid J^2\) ，当 \(J\) 是子树公因子，再乘一次 \(J\) 就能产生因子 \(I\) ：

\[ g_{u, i} = \min_{J | a_u \land I \mid J^2} f_{u, j} + 1 \]

Q ：为什么不像下面这样写呢？

\[ g_{u, i} = \min_{I \mid J^2} g_{u, j} + 1 \]

A ：如果 \(j \gt i\) ，还没算 \(g_{u, j}\) 呢。

做完了。整体复杂度不超过 \(O(n \cdot 32^2)\) 。预处理出对于每个 \(I\) 可选的 \(J\) ，会有少量优化。

#include 
#define int long long
#define ld long double
#define pii pair
using namespace std;
constexpr int INF = 2e12;
constexpr bool DBG = 0;constexpr int N = 2e5 + 5, L = 55;int n, k, a[N], f[N][L], g[N][L];
vector e[N];
int fac[L], tot;
vector wt[L];void dfs(int u, int fa) {for (int v : e[u]) {if (v != fa) dfs(v, u);}for (int i = 1; i <= tot; ++i) {f[u][i] = 0;for (int v : e[u]) {if (v != fa) f[u][i] += g[v][i];}}for (int i = 1; i <= tot; ++i) {g[u][i] = (a[u] % fac[i]) ? INF : f[u][i];for (int j : wt[i]) {if (a[u] % fac[j] == 0) g[u][i] = min(g[u][i], f[u][j] + 1);}}
}inline void solve() {cin >> n >> k;for (int i = 1; i <= n; ++i) e[i].clear();for (int i = 1; i <= n; ++i) cin >> a[i];for (int i = 1, u, v; i < n; ++i) {cin >> u >> v;e[u].push_back(v);e[v].push_back(u);}tot = 0;for (int x = 2; x <= a[1]; ++x) {if (a[1] % x == 0) fac[++tot] = x;}for (int i = 1; i <= tot; ++i) {wt[i].clear();for (int j = 1; j <= tot; ++j) {if (j != i && fac[j] * fac[j] % fac[i] == 0) wt[i].push_back(j);}}dfs(1, 1);int ans = a[1];for (int i = 1; i <= tot; ++i) {if (f[1][i] < k) ans = max(ans, a[1] * fac[i]);}cout << ans << "\n";
}signed main() {ios::sync_with_stdio(false);cin.tie(nullptr);int _ = 1;cin >> _;while (_--) solve();return 0;
}

---