题目描述

难度分:$2600$

输入$T(\leq 5 \times 10^4)$表示$T$组数据。所有数据的$n$之和$\leq 2 \times 10^5$。

每组数据输入$n(2 \leq n \leq 10^5)$，$k(0 \leq k \leq n)$和长为$n$的数组 $a(1 \leq a[i] \leq 1000)$。

然后输入一棵无向树的$n-1$条边，节点编号从$1$开始。根节点为$1$。节点$i$的点权为$a[i]$。

你可以执行如下操作至多$k$次：

• 选择一个没有操作过的节点$v$和一个整数$x$，其中$x$必须满足$x$是子树$v$中所有点权的公约数。然后把子树$v$中的每个点权都乘上$x$。

输出操作后，$a[1]$最大是多少。

输入样例

2
5 2
24 12 24 6 12
1 2
1 3
2 4
2 5
5 3
24 12 24 6 12
1 2
1 3
2 4
2 5

输出样例

288
576

算法

树形DP

比较容易看出来的是每次选择的$x$都需要是$a[1]$的因子，不然是没有用的，并且我们自底向上操作是最划算的。而每个节点只能操作一次，因此也比较容易能够想到树形DP。

状态定义

$f[u][c]$表示以$u$为根的子树中所有节点的点权都为$c$的倍数时的最小操作次数。因此我们$DFS$完之后，直接遍历$a[1]$的所有因子$factor$，只要$f[1][factor] \leq k$就说明所有节点都可以变成$factor$的倍数，最大的$a[1] \times factor$就是答案。

状态转移

以当前节点为根的子树可操作也可不操作，有这两种策略：

1. 如果不操作，那么$f[u][c]=\Sigma_vf[v][c]$其中$v$是$u$的子节点，并且要求$c|a[u]$（$b|a$表示$a$能被$b$整除）。
2. 如果操作，为了使得$c|(a[u] \times j)$成立，我们找到最小的因子$j$就可以了（即最小的$j$满足$c|j^2$，因为为了$a[1]$最大，我们每一步操作需要乘以最大因子，那么$f[u][c]$的转移来源就应该是$f[v][j]$。子节点的点权乘以$j$就会变成$j^2$的倍数，那此时要想达成$c|(a[u] \times j)$就还要满足$j|a[u]$）。状态转移方程为$f[u][c]=1+\Sigma_{v}f[v][j]$。

复杂度分析

时间复杂度

$DFS$遍历一遍树的时间复杂度为$O(n)$，每个节点需要枚举因子$j$，而$[1,1000]$范围内因子的最大个数为$32$，所以整体的时间复杂度为$O(32n)$。

空间复杂度

树的邻接表空间复杂度为$O(n)$。$[1,1000]$中每个数的因子存入数组$d$中，$d[i]$中为$i$的因子，空间复杂度可以看成是个常数较大的$O(n)$。预处理出每个数$i$满足$i|j^2$的最小数$g[i]=j$存入到$g$数组中，这个空间可以开成常数的，但是我在实现的时候直接开了$O(n)$。瓶颈在于DP矩阵$f_{n \times 1000}$，它的空间复杂度为$O(1000n)$，也是整个算法的额外空间复杂度。

C++ 代码

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int INF = 0x3f3f3f3f;
const int N = 100005;

vector<int> d[N];
int g[N];  // 最小的g[i]满足i|g[i]*g[i]
int a[N];
vector<int> graph[N];
int f[N][1005];

void dfs(int u, int fa) {
    for(auto v: graph[u]) {
        if(v == fa) continue;
        dfs(v, u);
    }
    for(auto c: d[a[1]]) {
        // 枚举根节点的因数
        f[u][c] = INF;     // 初始化为无效状态
        // 第一种转移
        if(a[u] % c == 0) {
            int t = 0;
            for(auto v: graph[u]) {
                if(v == fa) continue;
                if(f[v][c] == INF) {
                    t = INF;
                    break;
                }
                t += f[v][c];
            }
            f[u][c] = min(f[u][c], t);
        }
        if(u == 1) {
            // 根节点没有第二种转移
            f[u][c]++;    // 根节点再进行一次操作
            continue;
        }
        // 第二种转移
        if(a[u] % g[c] == 0) {
            int t = 1;
            for(auto v: graph[u]) {
                if(v == fa) continue;
                if(f[v][g[c]] == INF) {
                    t = INF;
                    break;
                }
                t += f[v][g[c]];
            }
            f[u][c] = min(f[u][c], t);
        }
    }
}

int main() {
    // 预处理[1,1000]内每个数的因数
    for(int i = 1; i <= 1000; i++) {
        for(int j = i; j <= 1000; j += i) {
            d[j].push_back(i);
        }
        for(int j = 1;; j++) {
            if(j * j % i == 0) {
                g[i] = j;
                break;
            }
        }
    }
    int T;
    scanf("%d", &T);
    while(T--) {
        int n, k;
        scanf("%d%d", &n, &k);
        for(int i = 1; i <= n; i++) graph[i].clear();
        for(int i = 1; i <= n; i++) scanf("%d", &a[i]);
        for(int i = 1; i < n; i++) {
            int u, v;
            scanf("%d%d", &u, &v);
            graph[u].push_back(v);
            graph[v].push_back(u);
        }
        dfs(1, 0);
        int ans = a[1];
        for(auto factor: d[a[1]]) {
            if(f[1][factor] <= k) ans = max(ans, a[1]*factor);
        }
        printf("%d\n", ans);
    }
    return 0;
}