Thanks Ghost0fSparta, Edited!

Here is my approach to problem D (Although I did a silly mistake during contest but was able to solve after the contest)

Firstly I rooted the tree at 1st node (you can root it at any node). I kept a map for every node which denotes the following — dp[u][gcd] = dist , where dist is maximum distance possible in a path that starts with a node that is in subtree of u and ends at node u and the gcd of the path is gcd.

How to calculate this?

This can be done using dfs. Initially for every node put dp[u][a[u]] = 1 if a[u] is not 1. Then do the following —

void dfs(int u, int p) {
    for(auto v: adj[u]) {
        if(v == p) continue;
        for(auto it: dp[v]) {
            int gcd = __gcd(a[u], it.F);
            if(gcd != 1)
                dp[u][gcd] = max(dp[u][gcd], it.S + 1);
        }
    }
}

Why do we need this?

For each node u we have two options -

1. Either choose two children x, y that are connected to node u such that dp[x][g1] = dist1 and dp[y][g2] = dist2 and gcd(g1, g2, a[u]) != 1, ans = max(ans, dist1 + dist2 + 1)
2. Choose any one of the child and go to the parent and repeat the same. For one child the ans is stored in dp itself.

This can be also incorporated in the same dfs as follows —

void dfs(int u, int p) {
    for(auto v: adj[u]) {
        if(v == p)
	    continue;
	dfs(v, u)
	if(__gcd(a[v], a[u]) != 1) {
	    for(auto i: dp[v]) {
		for(auto j: dp[u]) {
		    if(__gcd(i.F, j.F) != 1) {
		        ans = max(ans, i.S + j.S);
		     }
		}
	    }
	}
	for(auto it: dp[v]) {
	    int gcd = __gcd(a[u], it.F);
	    if(gcd != 1)
	        dp[u][gcd] = max(dp[u][gcd], it.S + 1);
	}
    }
}

The trick is that when we are visiting i'th child, the ans upto (i — 1)'th child would already be included in the parent's dp and could be used.

When tester got no chill! :p