P5243 [USACO19FEB] Moorio Kart P

Bessie and Farmer John enjoy goat go-kart racing. This competition is very similar to the go-kart racing that other people like, except that the karts are pulled by goats, and the track consists of farmland. The farmland consists of $N$ pastures and $M$ roads, and each road connects two pastures. Define a farm as a set of two or more pastures such that within the same farm, every pasture can reach any other pasture in the farm along a sequence of **unique** roads. The entire farmland may consist of multiple farms. Suppose there are $K$ farms in the graph. Bessie wants to create a goat go-kart track by adding $K$ roads of length $X$ to connect all $K$ farms. Each farm should be visited only once, and within each farm, at least one road must be traversed. To make the track more interesting for the contestants, the length of the track should be at least $Y$. Bessie wants to know the sum of track lengths of all such interesting tracks. If two farms are directly connected in one track, but those two farms are not directly connected in another track, then these two tracks are considered different. --- Formal statement: You are given a forest with $K$ connected components, with weighted edges. You need to add $K$ edges of length $X$ so that the entire graph becomes a unicyclic graph (a tree with exactly one cycle). Each original connected component must have at least one edge on the cycle, and all newly added edges must be on the cycle. Find the sum of the cycle lengths over all valid constructions whose cycle length is $\ge Y$.

The first line contains four integers $N, M, X, Y$ ($1 \leq N \leq 1500, 1 \leq M \leq N-1, 0 \leq X, Y \leq 2500$). The next $M$ lines each contain three integers: $A_i, B_i, D_i$ ($1 \leq A_i, B_i \leq N, 0 \leq D_i \leq 2500$), indicating that there is a road of length $D_i$ between pastures $A_i$ and $B_i$. It is guaranteed that there is at most one road directly connecting any two pastures, and there are no self-loops.

Output the sum of lengths of all interesting tracks modulo $10^9+7$.

There are 6 valid track constructions: - 1 --> 2 --> 4 --> 5 --> 1 (length 11). - 1 --> 2 --> 5 --> 4 --> 1 (length 11). - 2 --> 3 --> 4 --> 5 --> 2 (length 12). - 2 --> 3 --> 5 --> 4 --> 2 (length 12). - 1 --> 2 --> 3 --> 4 --> 5 --> 1 (length 15). - 1 --> 2 --> 3 --> 5 --> 4 --> 1 (length 15). Among them, the last 4 tracks satisfy the requirement that the total track length is at least 12, and the sum of their lengths is 54. Subtasks: For $70\%$ of the testdata, $N, Y \leq 1000$. Translated by ChatGPT 5