// verified: https://yukicoder.me/submissions/1102184 // verified: https://codeforces.com/contest/2063/submission/326584003 // verified: https://atcoder.jp/contests/abc359/submissions/67289775 #include #include using namespace std; // 参考: https://nyaannyaan.github.io/library/tree/dsu-on-tree.hpp.html // ただし、パスクエリにもこたえられるように、dfsで探すようにしている template struct DSUonTree { vector> g; vector sz; // 部分木クエリにeuler tourで答えるように、iの子要素を列挙する // ただし、lca(u,v)に対して、条件を満たす(u,v)を数える場合はdfs的に潜るので、これらを使って列挙しても意味がない vector euler,up,down; // eulerとかを途中で使う用のcount int idx_; // 根 int root; // sub tree計算用 void dfs1(int cur, int par = -1){ sz[cur] = 1; if ((int)g[cur].size() >= 2 && g[cur][0] == par) swap(g[cur][0], g[cur][1]); for(T &v : g[cur]){ if (v == par) continue; dfs1(v,cur); sz[cur] += sz[v]; if (sz[v] > sz[g[cur][0]]) swap(v, g[cur][0]); } } void dfs2(int cur, int par = -1) { euler[idx_] = cur; down[cur] = idx_++; for(auto &v : g[cur]){ if (v == par) continue; dfs2(v, cur); } up[cur] = idx_; } DSUonTree(vector> &_g,int _root = 0) : g(_g), sz(_g.size()), euler(_g.size()), up(_g.size()), down(_g.size()), idx_(0), root(_root){ dfs1(root); dfs2(root); } template void run(UPDATE &update, QUERY &query, CLEAR &clear, RESET &reset) { auto dfs_update = [&](auto rc,int cur,int par = -1) -> void { update(cur); for(int u:g[cur]){ if(u==par) continue; rc(rc,u,cur); } return; }; auto dfs_calc = [&](auto rc,int lca,int cur,int par = -1) -> void { query(cur,lca); for(int u:g[cur]){ if(u==par) continue; rc(rc,lca,u,cur); } return; }; auto dsu = [&](auto rc, int cur, int par = -1, bool keep = false) -> void { for (int i = 1; i < (int)g[cur].size(); i++){ if (g[cur][i] != par) rc(rc, g[cur][i], cur, false); } if(sz[cur]!= 1) rc(rc, g[cur][0], cur, true); if (sz[cur] != 1){ for(int i=1;i #include using namespace std; using namespace atcoder; using mint = modint998244353; const int MX = 1000000; int pr[MX + 10]; int a[500010]; mint ans[500010]; mint pw(mint k,int x){ mint ret = 1; while(x){ if(x&1) ret *= k; k *= k; x /= 2; } return ret; } int main(){ std::ios_base::sync_with_stdio(false); std::cin.tie(nullptr); int i,j,n; cin >> n; for(i=0;i> a[i]; for(i=2;i<=MX;i++){ if(pr[i]) continue; for(j=i;j<=MX;j+=i) pr[j] = i; } vector> g(n); for(i=0;i> u >> v; u--; v--; g[u].push_back(v); g[v].push_back(u); } mint c = 1; vector um(MX + 1),hs; // node iの中身をglobalなデータに反映する auto update = [&](int i) { int x = a[i]; while(x>1){ int p = pr[x],e = 0; mint y = 1; while(x%p==0){ x /= p; e++; if(e>um[p]) y *= p; } if(um[p]==0) hs.push_back(p); if(um[p] dst(g); dst.run(update,query,clear,reset); for(i=0;i