提出 #31088955

---

ソースコード 拡げる

#include <bits/stdc++.h>

template < typename T >
inline void read(T &cnt)
{
	cnt = 0; char ch = getchar(); bool op = 1;
	for (; ! isdigit(ch); ch = getchar())
		if (ch == '-') op = 0;
	for (; isdigit(ch); ch = getchar())
		cnt = cnt * 10 + ch - 48;
	cnt = op ? cnt : - cnt;
}
const int N = 1e5 + 10;
const int mod = 998244353;
int n, a[N], MAX;
int head[N], nxt[N * 2], to[N * 2], tot;

inline void add(int u, int v)
{
	nxt[++ tot] = head[u];
	head[u] = tot;
	to[tot] = v;
}

int vis[N], phi[N], prime[N], cnt;

bool cango[N], visit[N];

inline void Make_Prime()
{
	phi[1] = 1;
	for (int i = 2; i <= MAX; ++ i)
	{
		if (! vis[i])
		{
			vis[i] = i;
			prime[++ cnt] = i;
			phi[i] = i - 1;
		}

		for (int j = 1; j <= cnt; ++ j)
		{
			if (prime[j] * i > MAX || vis[i] < prime[j])
				break;
			vis[i * prime[j]] = prime[j];
			phi[i * prime[j]] = (i % prime[j]) ? (phi[i] * (prime[j] - 1)) : (phi[i] * prime[j]);
		}
	}
}

long long siz[N], dep[N], now, ans;
std::vector < int > V[N];

inline void dfs(int u, int fa)
{
	siz[u] = dep[u] = 1; visit[u] = true;
	for (int i = head[u]; i; i = nxt[i])
	{
		int v = to[i];
		if (v == fa || ! cango[v] || visit[v]) continue;
		dfs(v, u); 
		(now += dep[u] * siz[v] % mod + siz[u] * dep[v] % mod) %= mod;
		(dep[u] += dep[v] + siz[v]) %= mod;
		(siz[u] += siz[v]) %= mod;
	}
}

int main()
{
	read(n);

	for (int i = 1; i <= n; ++ i)
	{	
		read(a[i]); MAX = std::max(MAX, a[i]);
		V[a[i]].push_back(i);
	}
	Make_Prime();
	for (int i = 1; i < n; ++ i)
	{
		int u, v; read(u), read(v);
		add(u, v); add(v, u);
	}

	for (int i = 1; i <= MAX; ++ i)
	{
		now = 0;
		std::vector < int > go; go.clear();
		for (int j = i; j <= MAX; j += i)
			for (int k = 0; k < (int)V[j].size(); ++ k)
			{
				go.push_back(V[j][k]);
				cango[V[j][k]] = 1;
			}
		if (go.size() > 1) 
		{
			for (int j = 0; j < (int)go.size(); ++ j)
				if (! visit[go[j]])
					dfs(go[j], 0);	
		}
		for (int j = 0; j < (int)go.size(); ++ j)
			visit[go[j]] = 0, cango[go[j]] = 0;
		ans += now * phi[i] % mod;
		ans %= mod;
	}
	std::cout << (ans + mod) % mod << std::endl;
	return 0;
}

提出情報

ジャッジ結果