Considering the tree as a rooted tree, we will solve it with DP (Dynamic Programming) on tree.

In this editorial, for vertices \(u\) and \(v\) on the tree,
let us define \(f(u,v)\) to be \(1\) if \(u=v\), or the number of vertices in the simple path connecting \(u\) and \(v\) (including endpoints) if \(u\neq v\).
In other words, for the distance of two vertices \(d(u,v)\), we always have \(f(u,v)=d(u,v)+1\).
Additionally, let \(g(u,v)\) be \(A_u\) if \(u=v\), or the value \(\gcd(A_{p_1},\ldots,A_{p_k})\) on the simple path connecting \(u\) and \(v\) if \(u\neq v\).
Here, for two distinct vertices, \(C(u,v)=f(u,v)g(u,v)\) holds.

From the initial state where each vertex is disconnected, in the post-order of DFS (Depth First Searching), we can repeat the operation of merging a tree \(T'\) rooted at \(r'\) to another tree \(T\) rooted at \(r\) by “appending \(r'\) as a direct child of \(r\),” so that we can reconstruct the original tree. This operation is done \(|T|-1\) times, same as the number of edges in the original tree.

Let us consider finding \(ans(T)=\displaystyle\sum_{i=1}^{|T|-1}\sum_{j=i+1}^{|T|}C(i,j)\) for each tree \(T\) obtained in this process and updating them. Here, for a rooted tree \(T\) rooted at \(r\), let \(cnt(T,x)\) denote the number of vertices \(v\) in \(T\) such that \(g(r,v)=x\), and \(sum(T,x)\) denote the sum of \(f(r,v)\) over the vertices \(v\) in \(T\) such that \(g(r,v)=x\).

When we already have the values for \(T_0\) (rooted at \(r_0\)) and \(T'\) (rooted at \(r'\), the value \(ans(T)\) for the merged tree \(T\) (rooted at \(r_0\)) can be found as

\[ ans(T)=ans(T_0)+ans(T')+\displaystyle\sum_{x}\sum_{y} \gcd(x,y)\times \left\{ cnt(T_0,x) sum(T',y)+ sum(T_0,x) cnt(T',y) \right\}. \]

The first and the second term \(ans(T_0)+ans(T')\) are the sum of \(f(u,v)g(u,v)\) over each pair of vertices in each tree, and the third term is the sum of \(f(u,v)\) over all the pairs of vertices, one of each belonging to \(T_0\) and the other to \(T'\).
Additionally, \(cnt(T,x)\) and \(sum(T,x)\) can be found by
\(cnt(T,x)=cnt(T_0,x)+\displaystyle\sum_{\gcd(r,y)=x}cnt(T',y)\) and \(sum(T,x)=sum(T_0,x)+\displaystyle\sum_{\gcd(r,y)=x}(sum(T',y)+cnt(T',y))\).

For the initial state consisting only of a single vertex \(v\), we have \(cnt(T,x)=sum(T,x)=(1\) if \(x=A_v\) or \(0\) otherwise\()\), \(ans(T)=0\).

By performing this merge operations repeatedly, the answer for the original problem can be found. Let us evaluate the computational complexity.

For \(x\) such that \(cnt(T,x)=0\), we do not have to store the values of \(cnt(T,x)\) and \(sum(T,x)\). The number of not such \(x\) is at most the number of divisors of \(A_r\) and also at most \(|T|\), so it is bounded from above by \(\min(|T|,D)\) where \(D\) is the maximum number of divisors of an integer no more than \(10^5\). Then, when merging, \(\min(|T_0|,D)\cdot \min(|T'|,D)\cdot \log(\max(A_i))+\min(|T_0|,D)+\min(|T'|,D)\) steps of computation is required, which is bounded by \(C_0\min(|T_0|,D)\min(|T'|,D)\), where \(C_0=\log(\max(A_i))+2\).

Therefore, the maximum number of steps required to compute against \(N\)-vertex tree, \(h(N)\), can be evaluated as

\[ h(N)\leq \displaystyle\max_{1\leq i\leq N-1}(h(i)+h(N-i)+C_0\min(i,D)\min(N-i,D)). \]

Also, we have \(h(1)=1\leq\frac{1}{2}C_0\). Here, \(h(N)\leq \frac{1}{2}C_0N^2\) holds for \(N\leq 2D\), and \(h(N)\leq \frac{1}{2}C_0( 3N-2D)D\) holds for \(N> 2D\). Therefore, the time complexity is \(O(ND\log(\max(A_i)))\). Since \(D=128\) for \(N=10^5\), it is fast enough. Therefore, the problem has been solved.