题目分析

题目要求在树上选出一个连通块，满足块内点权的gcd为s1且lcm为s2。由于s1整除所有a_i且a_i整除s2，可以将所有点权除以s1，问题转化为求gcd为1且lcm为s2/s1的连通块数量。

解题思路

1. 质因数分解：对s2/s1进行质因数分解，得到其所有质因子。由于s2无平方因子，每个质因子仅出现一次。
2. 状态压缩：将每个点权表示为质因子的二进制状态（某一位为1表示包含对应质因子）。
3. 容斥原理：利用容斥原理计算满足lcm为目标值的连通块数量。具体来说，对于每个子集，计算包含该子集所有质因子的连通块数量，再通过容斥调整符号。
4. 树形DP：在树上进行DFS，计算以每个节点为根的满足条件的连通块数量。

代码实现

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define il inline
#define N 1005
#define M 15
il ll rd() {
    ll s = 0, w = 1;
    char ch = getchar();

    for (; ch < '0' || ch > '9'; ch = getchar())
        if (ch == '-')
            w = -1;

    for (; ch >= '0' && ch <= '9'; ch = getchar())
        s = ((s << 1) + (s << 3) + ch - '0');

    return s * w;
}
const ll P = 1e9 + 7;
ll n = rd(), s1 = rd(), x = rd(), a[N], f[N], u, v, ans, p[N], cnt;
vector <ll> e[N];
void dfs(ll u, ll fa, ll s) {
    f[u] = 1;

    for (int i = 0; i < e[u].size(); i++) {
        ll v = e[u][i];

        if (v == fa)
            continue;

        dfs(v, u, s);

        if (((a[u] ^ a[v]) & s) == 0)
            f[u] = (f[u] + f[u] * f[v] % P) % P;
    }
}
int main() {
    x /= s1;

    for (int j = 2; j <= 50; j++)
        if (x % j == 0)
            x /= j, p[++cnt] = j;

    for (int i = 1; i <= n; i++) {
        x = rd() / s1;

        for (int j = 1; j <= cnt; j++)
            if (x % p[j] == 0)
                a[i] |= (1 << (j - 1));
    }

    for (int i = 1; i < n; i++) {
        u = rd(), v = rd();
        e[u].push_back(v);
        e[v].push_back(u);
    }

    for (int s = 0; s < (1 << cnt); s++) {
        ll res = 0;

        for (int j = 1; j <= cnt; j++)
            if (s & (1 << (j - 1)))
                res ^= 1;

        dfs(1, 0, s);

        for (int i = 1; i <= n; i++)
            if (res)
                ans -= f[i];
            else
                ans += f[i];
    }

    ans = (ans % P + P) % P;
    printf("%lld", ans);
    return 0;
}

代码解释

1. 输入处理：读取输入数据，将s2除以s1，并对结果进行质因数分解。
2. 状态压缩：将每个点权转换为质因子的二进制表示。
3. DFS遍历：对于每个子集s，计算包含该子集所有质因子的连通块数量。DFS过程中，f[u]表示以u为根的满足条件的连通块数量。
4. 容斥计算：根据子集大小的奇偶性调整符号，累加所有子集的结果，最终得到答案。