I've got a weighted tree graph, where all the weights are positive. I need an algorithm to solve the following problem.
How many pairs of vertices are there in this graph, for which the sum of the weights of edges between them equals $C$?
I thought of a solutions thats $O(n^2)$
For each vertex we start a DFS from it and stop it when the sum gets bigger than $C$. Since the number of edges is $n-1$, that gives us obviously an $O(n^2)$ solution.
But can we do better asymptotics-wise?
If the weights are integers and $C$ is small relative to $n$, you may prefer an $O(nC)$ algorithm:
Select a root node, and process the vertices in postorder, For each vertex compute an array of how many vertices below it have distances $0, 1, 2, \ldots, C$ from it. Two such arrays can be combined to one in $O(C)$, time, while also counting how many paths of total weight $C$ span the particular two subtrees they describe.