I solved that problem with LCA

The idea is to have the information stored for all the nodes up to a parent that is at a distance of 2 ^ k. Now the problem is the following:

1 — First of all, to have the information stored, you need a precalculation and you have to know for each node the number of paths in the sub-tree of the parent node of u that pass only for the parent u and not for u. Now with that information we can have saved the solution for each node by uploading to a parent at a distance of 2 ^ k.

2 — After uploading each node to the LCA (u, v) you have to take into account other paths that were left uncounted, for example we do not count the number of roads that pass only by u and only by v from their respective sub-trees unless that one of the two is the LCA(u, v) and the amount is equal to: The number of paths that start from the sub tree of v and pass through v and not by any of their parents is equal to: Let's say that for son u of v has sub[i] nodes in his subtree then that amount of paths can be found in the following way ans = sub[v] + (sub[i1] * sub[i2]) + (su [i1] * sub[i3]) + ... (sub[i1] * sub[in]) + (sub[i2] * sub [i3]) + .... sub [in-1] * sub [in]

and also missing the paths that come from above the LCA(u, v) rooting the tree from any node by default but it is very easy to calculate.

And in the end you have the preprocessing in O (n log n) and the queries in O (log n).

For more clarity see my code.

my solution

Excuse me for my English grief.