Given a weighted tree ($$T$$) and an integer $$MAXW$$, count the number of weighted graphs whose non-negative edges weight at most $$MAXW$$ and $$T$$ is an MST (minimum spanning tree) for that graph. Output the result modulo $$987654319$$.
Input
The first line of input contains two integers $$n$$ and $$MAXW$$, the number of vertices of the aforementioned tree and the maximum allowed weight of an edge respectively ($$1 \le n \le 300000$$).
The next $$n-1$$ lines describes the tree. Each of which contain three integers, $$v_i$$, $$u_i$$ and $$w_i$$, meaning that there's and edge connecting vertices $$v_i$$ and $$u_i$$ with weight equal to $$w_i$$ ($$0 \le MAXW, w_i \le 10^9$$).
It's guaranteed that the given graph forms a tree.
Output
Print only one integer, the number of desired graphs modulo $$987654319$$.
3 4 1 2 3 1 3 2
3
It can easily be shown that the only other graph edge which isn't present in the tree ($$2-3$$) should weight at least 3. So there are 4 graphs in total matching the condition (one of them doesn't contain this edge).
Please login to use the editor
You need to be logged in to access the code editor
Loading...
Please wait while we load the editor