该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

Description

【问题描述】
你有一棵以 1 为根的树，统计点对$ (x, y)$，满足 $a_{lca(x,y)}$ 是 $a_x$ 和 $a_y$ 的公约数。注意当$x \neq y$ 时 $(x, y)$ 和 $(y, x)$ 视为不同的点对。

【输入格式】
第一行一个整数 $n$。
第二行 $n$ 个整数 $a_i$。
第三到 $n + 1$ 行，每行两个整数，表示树上的边。

【输出格式】
一行一个整数表示答案。

【样例 1 输入】
5
2 3 2 5 4
1 2
1 3
2 4
2 5

【样例 1 输出】
11

【样例 1 解释】
以下点对满足条件：(1, 1),(1, 3),(1, 5),(2, 2),(3, 1),(3, 3),(3, 5),(4, 4),(5, 1),(5, 3),(5, 5)。

Hint

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N=1e5+10;
LL a[N], ans, c[N]; vector<int> G[N];
//c[i]表示当前以i为因子的点的个数
void add(LL x){
    for(LL i=1; i*i<=x; i++) if(x%i==0){
        if(i*i!=x) c[i]++; //平方数不重复加
        c[x/i]++;
    }
}
void dfs(int x, int fa){
    LL pre=c[a[x]]; //pre表示在x的子树之前的累计
    add(a[x]); //把a[x]放进去
    //当前递归x是找以x为lca的点对个数
    for(int y: G[x]) if(y!=fa){
        LL t=c[a[x]];  //t表示在y的子树之前的累计
        dfs(y, x);
        ans+=(c[a[x]]-t)*(t-pre);
        //加上y的子树的累计乘以在y之前x的子树的累计
    }
}
int main(){
    //freopen("a.in", "r", stdin);
    int n; scanf("%d", &n);
    for(int i=1; i<=n; i++) scanf("%lld", &a[i]);
    for(int i=1; i<n; i++){
        int x, y; scanf("%d%d", &x, &y);
        G[x].push_back(y);
        G[y].push_back(x);
    }
    memset(c, 0, sizeof(c));
    ans=0; dfs(1, 0);
    printf("%lld\n", ans*2+n); //乘上xy重复的加上xy相同的
    return 0;
}