Submission #30998243

---

Source Code Expand

#include<bits/stdc++.h>
#include<atcoder/all>
using namespace std;
using namespace atcoder;
using mint=modint998244353;

vector<int>A;  //A[i]=頂点iに書かれた値
vector<vector<int>>idx;  // idx[i]=値iが書かれた頂点たちからなるvector
vector<vector<int>>G;  // 隣接リスト
vector<int>visited;  // dfs時のフラグ
vector<mint>ans;  // ans[i]=パス上の頂点のgcdがiになるような頂点対の個数

void dfs(int v,int pre,int d,vector<int>&ans){
	//vを根とし、dの倍数のみが書かれた頂点からなる部分木Tを考え、
	//Tの各頂点について部分木の頂点数を求め、ansの末尾に追加する
	//ans.back()がvの部分木の頂点数になるようにする
	visited[v]=d;
	int cnt=1;
	for(auto vv:G[v])if(vv!=pre&&A[vv]%d==0){
		dfs(vv,v,d,ans);
		cnt+=ans.back();
	}
	ans.push_back(cnt);
}


int main(){
	int N;
	cin >> N;
	idx.resize(100010);
	A.resize(N);
	for(int i=0;i<N;i++){
		int a;
		cin >> a;
		idx[a].push_back(i);
		A[i]=a;
	}
	G.resize(N);
	for(int i=0;i<N-1;i++){
		int x,y;
		cin >> x >> y;
		G[x-1].push_back(y-1);
		G[y-1].push_back(x-1);
	}

	visited.resize(N);
	ans.resize(100010);
	mint kotae=0;
	for(int i=100000;i>0;i--){
		for(int d=i;d<=100000;d+=i){
			for(int v:idx[d])if(visited[v]!=i){
				vector<int>ret;
				dfs(v,-1,i,ret);
				mint num=ret.back();
				ret.pop_back();
				for(int x:ret)ans[i]+=(num-x)*x;
				ans[i]+=num*(num-1)/2;
			}
		}
		for(int d=2*i;d<=100000;d+=i)ans[i]-=ans[d];
		kotae+=ans[i]*i;
	}

	cout << kotae.val();

}

Submission Info

Judge Result