Applying the centroid decomposition, it is sufficient to find the answer for paths passing through the root.

We consider two cases depending on whether the endpoint of the path is the root or not. If it is root, one can naively perform BFS (Breadth-First Search).

Otherwise, for each vertex \(v\), count how many times the path between vertex \(v\) and the root contributes to the answer. Let \(c_1,\ldots,c_k\) be the children of the root, and suppose that vertex \(v\) is contained in the subtree \(c_i\).

Then, the number of times the path between vertex \(v\) and the root contributes to the answer is found as

(the number of vertices \(u\) contained in the current tree such that \(A_v = A_u\)) - (the number of vertices \(u\) in the subtree \(c_i\) such that \(A_v = A_u\)).

The values required can all be found sin a DFS (Depth-First Search), so the problem has been solved.