Sponsored
Sponsored
Use these hints if you're stuck. Try solving on your own first.
Root the tree at any node.
Define a 2D array <code>freq[node][weight]</code> which saves the frequency of each edge <code>weight</code> on the path from the root to each <code>node</code>.
The frequency of edge weight <code>w</code> on the path from <code>a</code> to <code>b</code> is equal to <code>freq[a][w] + freq[b][w] - freq[lca(a,b)][w] * 2</code>, where <code>lca(a,b)</code> is the lowest common ancestor of <code>a</code> and <code>b</code> in the tree.
<code>lca(a,b)</code> can be calculated using binary lifting algorithm or Tarjan algorithm.