この問題は、Heavy Light Decomposition（以下 HLD と呼称） と呼ばれるアルゴリズムにより解くこともできます。

HLD については、以下の記事が詳しいので参照ください。

• ABC 269-Ex 解説

• CodeForces の記事

HLD は、木のパスに対するクエリを \(\mathrm{O}(\log N)\) 個の列へのクエリに分解できるのでした。列に対する問題は、単純な点更新区間加算であり、これは fenwick tree を用いて \(\mathrm{O}(\log N)\) で解けます。よってこの問題は \(\mathrm{O}(N+Q\log^2 N)\) で解けます。