Submission #35150044

---

Source Code Expand

#include <bits/stdc++.h>
#include <atcoder/modint>
using mint = atcoder::modint998244353;
using namespace std;
#define rep(i,a,n) for (int i=a;i<(int)n;i++)
int read(){int r;scanf("%d",&r);return r;}

const int N = 1e5;

int a[N+10];
vector<int> G[N+10]; // G[u] = {v}
vector<int> ys2i[N+10]; // ys2i[因数] = {点id}
bool vis[N+10];
int siz[N+10]; // 当前子树大小

int dfs1(int u,int fa,int d) { // return 子树大小
  vis[u] = true;
  siz[u] = 1;
  for(auto v:G[u]) if(v!=fa && a[v]%d==0) siz[u] += dfs1(v,u,d);
  return siz[u];
}

mint dfs2(int u, int fa, int sz/*联通块总大小*/, int d){
  vis[u] = false;
  mint r = 0;
  mint pre = sz - siz[u] + 1; // 父方向 节点数 包括u; 树上换根 + 前缀和dp
  r += pre;
  for(auto v : G[u]) if(v!=fa && a[v]%d==0){
    r += pre * siz[v]; // 当前v级子树的点和 前面点覆盖了u的路径数
    pre += siz[v];
    r += dfs2(v, u, sz, d);
  }
  return r;
}

int phi[N+10]; // phi(i)
int main() {
  { // calc phi
    iota(phi,phi+N+1,0);
    vector<bool> p(N+1,0); // prime vis
    rep(i,2,N+1) if(!p[i]) for(int j=i;j<=N;j+=i){ // j = ki
      p[j] = true;
      (phi[j] /= i) *= (i-1);
    }
  }
  int n = read();
  {
    vector<vector<int>>ys(N+1); // ys[i] = {i的因数}
    rep(i,1,N+1) for(int j=i;j<=N;j+=i) ys[j].push_back(i); // 计算因子
    rep(i,0,n) {
      a[i] = read(); // 0-index
      for(auto x:ys[a[i]]) ys2i[x].push_back(i);
    }
    rep(i,1,n){
      int u = read()-1;
      int v = read()-1;
      G[u].push_back(v);
      G[v].push_back(u);
    }
  }
  mint ans = 0;
  rep(d,1,N+1){ // \phi(d) * 路径上全是d的倍数的路径长度和 = \phi(d) * sum(每个点被边覆盖的次数)
    mint r = 0;
    for(auto u:ys2i[d]) if(!vis[u]) dfs1(u,u,d);
    for(auto u:ys2i[d]) if(vis[u]) r += dfs2(u,u,siz[u],d); 
    ans += phi[d] * r;
  }
  rep(i,0,n) ans -= a[i]; // 去掉单点
  printf("%d\n", ans.val());
  return 0;
}

Submission Info

Compile Error

./Main.cpp: In function ‘int read()’:
./Main.cpp:6:23: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
    6 | int read(){int r;scanf("%d",&r);return r;}
      |                  ~~~~~^~~~~~~~~

Judge Result