dp[u][d]表示以u为根的子树，包含u这个节点且公因数为d的最大链长（不横跨两个子树，这里的链指的是u节点和它的一个子树的部分点形成的链）。不过答案链长可能会横跨u的两个子树，这个在转移的时候考虑到了。

在cf上wa on 6，比答案多1。代码里面有部分注释

#include<bits/stdc++.h>
using namespace std;

#define endl '\n' 
#define int long long
const int N = 1e6+5, mod = 1e9+7;

int a[N];
vector<int> g[N];
map<int,int> dp[N];

void solve(){

    int n;
    cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i];
    for(int i=1;i<n;i++) {
        int a, b;
        cin>>a>>b;
        g[a].push_back(b);
        g[b].push_back(a);
    }

    int ans = 0;
    auto dfs = [&](auto dfs, int u, int fa) ->void {
        dp[u][a[u]] = 1;
        if(a[u]!=1) ans = max(ans,1ll);
        for(int v : g[u]) {
            if(v==fa) continue;
            dfs(dfs,v,u);
            for(auto [x,y] : dp[v]) {
                int d = __gcd(x,a[u]);
                if(dp[u].count(d)) {
                    if(d!=1) ans = max(ans,dp[u][d]+y); // 横跨u的两个子树形成的链
                    dp[u][d] = max(dp[u][d],y+1); // 更新最大链长，不横跨子树，只含u和它的一个子树
                }
                else {
                    dp[u][d] = y+1;
                }
                if(d!=1) ans = max(ans,dp[u][d]); 
            }
        }
    };

    dfs(dfs,1,0);

    cout<<ans<<endl;

} 

signed main() {

    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);

    // int T;
    // cin>>T;
    // while(T--)
    solve();
}