重心分解を用いることで、根を通るパスに対する答えが求められれば良いです。

パスの端点が根かどうかで場合分けします。根のときは、愚直に BFS などを行えばよいです。

そうでない場合、各頂点 \(v\) について、頂点 \(v\) と根を結ぶパスが何回答えに寄与するかを数えましょう。根の子が \(c_1,\ldots,c_k\) として、頂点 \(v\) は部分木 \(c_i\) に含まれるとします。

このとき、頂点 \(v\) と根を結ぶパスが答えに寄与する回数は、

(今見ている木に含まれる \(A_v = A_u\) を満たす頂点 \(u\) の個数 - 部分木 \(c_i\) に含まれる \(A_v = A_u\) を満たす頂点 \(u\) の個数)

として求まります。この計算に必要な値は全て dfs により求めることが出来ます。よってこの問題を解くことが出来ました。