Nhận xét: Mọi số nguyên dương ~N~ đều có thể được phân tích dưới dạng: ~p_1^{m_1} \times p_2^{m_2}...\times p_k^{m_k}~. Trong đó, ~p_i~ là các số nguyên tố, ~m_i~ là các số nguyên dương. Như vậy, số ước của ~N~ là: ~\sigma_0(N) = (m_1+1) \times (m_2+1)...\times (m_k+1)~, phần chứng minh bạn đọc có thể đọc tại đây.

Như vậy, để đếm tổng số ước của tích các số trong dãy, ta cần đếm tổng số mũ của từng thừa số nguyên tố xuất hiện trong tích đó, sau đó dùng công thức trên để tính ~\sigma_0(N)~.

Ta sẽ giải quyết bài này theo hướng quy hoạch động trên cây. Khi xét đến cây con thứ ~u~, giả sử ta đã tính được đáp án của cây con ~v~ gốc ~u~, ta có thể cập nhật đáp án ~dp_u = dp_u \cdot dp_v~. Gọi ~p(v)~ là tích các số trong cây con gốc ~v~, ~p(u)~ là tích các số trong cây con gốc ~u~ nhưng không tính các phần tử cây con gốc ~v~, khi thực hiện cập nhật trên sẽ cho kết quả không đúng, xét thừa số nguyên tố ~k~ bất kì thuộc ~p(u)~ và ~p(v)~ có số mũ lần lượt là ~a~ và ~b~, khi thực hiện cập nhật đáp án như trên sẽ có đáp án sẽ là ~...\times (a+1) \times (b+1)~, nhưng đáp án đúng phải là ~...\times (a+b+1)~.

Để giải quyết vấn đề trên, với mỗi thừa số nguyên tố ~k~ chung của ~p(u)~ và ~p(v)~, ta sẽ loại bỏ ~(a+1) \times (b+1)~ trong đáp án và thay ~a+b+1~ vào bằng phép chia và nhân.

Để tối ưu quy trình cập nhật đáp án, ta sẽ thực hiện kĩ thuật small to large trên cây để thực hiện merge đáp án các cây con với độ phức tạp ~O(n^2)~. Ngoài ra, còn có thể tối ưu bằng kĩ thuật **DSU on tree** để đạt được độ phức tạp thấp hơn.

#include <bits/stdc++.h>

using namespace std;

const int N = 1e5, mod = 1e9 + 7;

int min_prime[N + 1], ans[N + 1], inv[20*N];
vector<int> a[N + 1];
map<int, int> f[N + 1];

void sieve()
{
    for (int i = 2; i*i <= N; i++)
        if (min_prime[i] == 0)
            for (int j = i*i; j <= N; j += i)
                if (min_prime[j] == 0) min_prime[j] = i;
    for (int i = 2; i <= N; ++i)
        if (min_prime[i] == 0) min_prime[i] = i;
}

void dfs(int u, int pre = 0)
{
    for (auto v : a[u])
    {
        if (v == pre) continue;
        dfs(v, u);
        ans[u] = 1ll*ans[u]*ans[v]%mod;
        if ((int)f[u].size() < (int)f[v].size()) swap(f[u], f[v]);
        for (auto x : f[v])
        {
            if (f[u][x.first])
                ans[u] = 1ll*ans[u]*(f[u][x.first]+x.second+1)%mod*inv[f[u][x.first]+1]%mod*inv[x.second+1]%mod;
            f[u][x.first] += x.second;
        }
    }
}

int main()
{    
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    freopen("tree.inp", "r", stdin);
    freopen("tree.out", "w", stdout);

    inv[1] = 1;
    for (int i = 2; i < 20*N; i ++) inv[i] = 1LL*(mod-mod/i)*inv[mod%i]%mod;

    sieve();

    int n, q;
    cin >> n >> q;

    for (int i = 1; i <= n; i++)
    {
        int x, cnt = 0;
        cin >> x;
        ans[i] = 1;
        while (min_prime[x])
        {
            if (!f[i][min_prime[x]])
            {
                ans[i] = 1ll*ans[i]*(cnt+1)%mod;
                cnt = 0;
            }
            cnt++;
            f[i][min_prime[x]]++;
            x /= min_prime[x];
        }
        ans[i] = 1ll*ans[i]*(cnt+1)%mod;
    }

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

    dfs(1);

    while (q--)
    {
        int u;
        cin >> u;
        cout << ans[u] << ' ';
    }

    return 0;
}