fork download
copy 
  1. /*Code by HsonW, 11/2 NH-Hue. Just a newbie <3*/
  2. /*mp<33333*/
  3. #include<bits/stdc++.h>
  4. using namespace std;
  5. using int64=long long;
  6. #define ll long long
  7. const int MOD=1e9+7;
  8. typedef pair<int,int> ii;
  9. const int M = 1e9+7;
  10. int n, q;
  11. vector<vector<int>> c;
  12. vector<int> a;
  13. vector<vector<pair<int, int>>> f;
  14. vector<ll> ans;
  15. ll pw(ll x, ll y = M - 2) {
  16.     ll r = 1;
  17.     while (y) {
  18.         if (y & 1) r = r * x % M;
  19.         x = x * x % M;
  20.         y >>= 1;
  21.     }
  22.     return r;
  23. }
  24. struct D {
  25.     unordered_map<int, int>* m;
  26.     ll v;
  27. };
  28. D dfs(int u) {
  29.     D d;
  30.     d.m = new unordered_map<int, int>();
  31.     d.v = 1;
  32.     for (auto& p : f[u]) {
  33.         (*d.m)[p.first] = p.second;
  34.         d.v = d.v * (p.second + 1) % M;
  35.     }
  36.     for (int v : c[u]) {
  37.         D t = dfs(v);
  38.         if (t.m->size() > d.m->size()) {
  39.             swap(d.m, t.m);
  40.             swap(d.v, t.v);
  41.         }
  42.         for (auto& kv : *t.m) {
  43.             int p = kv.first, e = kv.second;
  44.             int o = (*d.m)[p];
  45.             d.v = d.v * pw(o + 1) % M;
  46.             int ne = o + e;
  47.             (*d.m)[p] = ne;
  48.             d.v = d.v * (ne + 1) % M;
  49.         }
  50.         delete t.m;
  51.     }
  52.     ans[u] = d.v;
  53.     return d;
  54. }
  55. int main() {
  56.     #define name "TREE"
  57.     ios::sync_with_stdio(0);
  58.     cin.tie(NULL);
  59.     if (fopen(name ".inp", "r")) {
  60.         freopen(name ".inp", "r", stdin);
  61.         freopen(name ".out", "w", stdout);
  62.     }
  63.     cin >> n >> q;
  64.     a.assign(n + 1, 0);
  65.     for (int i = 1; i <= n; i++) cin >> a[i];
  66.     vector<vector<int>> g(n + 1);
  67.     for (int i = 0, u, v; i < n - 1; i++) {
  68.         cin >> u >> v;
  69.         g[u].push_back(v);
  70.         g[v].push_back(u);
  71.     }
  72.     c.assign(n + 1, {});
  73.     vector<int> s = {1}, p(n + 1, 0);
  74.     for (int i = 0; i < (int)s.size(); i++) {
  75.         int u = s[i];
  76.         for (int v : g[u]) if (v != p[u]) {
  77.             p[v] = u;
  78.             c[u].push_back(v);
  79.             s.push_back(v);
  80.         }
  81.     }
  82.     int A = *max_element(a.begin() + 1, a.end());
  83.     vector<int> sp(A + 1);
  84.     for (int i = 2; i <= A; i++) if (!sp[i]) for (int j = i; j <= A; j += i) if (!sp[j]) sp[j] = i;
  85.     f.assign(n + 1, {});
  86.     for (int i = 1; i <= n; i++) {
  87.         int x = a[i];
  88.         while (x > 1) {
  89.             int p = sp[x], cnt = 0;
  90.             while (x % p == 0) x /= p, cnt++;
  91.             f[i].emplace_back(p, cnt);
  92.         }
  93.     }
  94.     ans.assign(n + 1, 0);
  95.     dfs(1);
  96.     while (q--) {
  97.         int u; 
  98.         cin >> u;
  99.         cout << ans[u] << (q ? ' ' : '\n');
  100.     }
  101.     return 0;
  102. }
  103.  
Success #stdin #stdout 0.01s 5320KB
comments (?)
stdin
copy 
6 5
2 1 3 4 2 4
1 2
1 3
2 4
2 5
3 6
1 2 3 4 5
stdout
copy 
14 4 6 3 2
https://ideone.com/vawLU4
language:
C++14 (gcc 8.3)
created:
1 day ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!