指定された頂点たちの最小共通祖先関係を保って木を圧縮してできる補助的な木（通称 Auxiliary Tree）を用いて解くことができます． Auxiliary Tree は以前の ABC で出題されているため，知らない方はそちらの解説を参考にしてください．（ABC の過去問）

\(A_i\) の値ごとに答えの寄与を求めます．各 \(x=1,2,\ldots,N\) について \(A_i=x\) であるような頂点集合を \(V_x\) としたときに \(\displaystyle\sum_{\substack{u,v\in V_x \\ u\lt v}} f(u,v)\) を求めればよく，これは \(V_x\) の Auxiliary Tree 上で木 dp をすればよいです．

実装例 (Python)