I can do it in $$$O(n\log^3 n)$$$time. Divide and Conquer on Tree: pick a node, count valid paths passing through that node, then delete the node and do the same for each component. The node to pick is the Centroid of the tree. So how to count the paths passing through some node $$$u$$$? Well, root the tree at $$$u$$$, let’s say $$$u$$$’s children are $$$v_1,v_2,\dots, v_k$$$, do a DFS on each $$$v_i$$$’s subtree computing length and weight of paths from $$$u$$$ to all nodes. Now for each node node $$$j$$$ in the subtree of $$$v_i$$$ (let’s say length and weight from $$$u$$$ to $$$j$$$ are $$$L_j$$$ and $$$W_j$$$ respectively) we need to count how many nodes $$$k$$$ (not belonging to $$$v_i$$$’s subtree) are there such that $$$L_k\le l-L_j$$$ and $$$W_k\le w-W_j$$$. For that we can use a 2D data structure: let’s suppose we have a matrix where in position $$$(i,j)$$$ there is the amount of nodes $$$x$$$ such that $$$L_x=i$$$ and $$$W_x=j$$$, we can use a 2D-Segment Tree to add +1 to some position and ask for sum of a subrectangle in the matrix in $$$O(\log^2 n)$$$, so final complexity is $$$O(n\log^3 n)$$$, this might fit in time.

1) Run the centroid decomposition algorithm

2) Let the centroid now be some node $$$v$$$

3) Write down all the nodes that lie in the same component with $$$v$$$ (the tree will split into components, because there were already some centroids earlier and we do not pass through them)

4) Sort these nodes by $$$dist[i][v]$$$ (distance from $$$i$$$ to $$$v$$$).

5) Build a fenwik tree in each node of which we will store decart tree. The key in the decart tree will be $$$w[i]$$$ ($$$w[i]$$$ is the sum of the weights of the edges on the path from $$$v$$$ to node $$$i$$$)

6) Iterate over the neighbors of node $$$v$$$ and delete all the subtree of this neighbor from the decart tree, so that we don't consider vertices from the same subtree, otherwise we can't guarantee that the shortest path between them passes through the centroid. Iterate through all the vertices of the subtree. Let us now choose a node $$$u$$$. So that the distance between the nodes is less than or equal to l, we must take some prefix of the array, such that for all i of this prefix, $$$dist[i][v] + dist[u][v] \leq l$$$ is executed (this can be done using binary search for $$$O(\log(n))$$$). Now in the fenwik tree, take the data prefix and find the number of nodes for $$$O(\log(n))$$$ such that $$$w[i] \leq w - w[u]$$$.

7) Divide the answer by $$$2$$$, because each pair is counted twice. Thus, the final asymptotics will be $$$O(n\log^3(n))$$$

Здесь поищи