(Analysis by Spencer Compton )

Let's think about what a valid track really looks like. Each farm is a tree, so what we have is a forest of $K$ trees. A track visits every tree and travels along a path with $\geq 1$ edge in it, then takes an edge of length $X$ to go to another tree. If we ignore the order in which we visit trees, and just find the sum of lengths for all $K$ paths (one path per tree) that have total length $\geq Y$, this might be easier to deal with.

For each tree we can calculate the distance between each distinct pair of nodes inside it. We use this to calculate the number of paths of length $i$ (for all $0 \leq i<Y$) and the number of paths of length $\geq Y$ as well as the sum of their lengths in O(N^2). We can group together all paths of length $\geq Y$ because no matter what paths you combine them with in the future, they will meet the required condition that they have length $\geq Y$.

Now, we just want to combine this information for all the trees. Since we will need to connect the $K$ trees with edges of length $X$, we can say we start with one path of length $K \times X$. Then we combine this information we have so far with each tree. We can say for any $i$ and $j$ that if the information we computed so far says we have $A$ paths of length $i$ that have total length $B$ and the current tree we are processing has $C$ paths of length $j$ that have total length $D$, then we could combine them such that we then have $AC$ paths of total length $AD+BC$. To account for all possible combinations, we would loop over all values of $i$ and $j$ in range $[0,Y]$ and have an $O(NY^2)$ algorithm.

Fortunately, we can speed this up. One observation is that when we have a very small tree then the number of distinct path lengths it can have is small. This is because a tree of size $N$ has $<N^2$ paths. At the same time, since we group together paths with length $\geq Y$, if N^2 is greater than Y we still only need to look at $Y$ different values of $j$. If we only loop over values of $j$ for each tree that have at least $1$ path of that length, our algorithm would likely be a lot faster. Such an algorithm would run in $O(YS)$ where $S$ is equal to the sum of the number of distinct path lengths in each tree (when we group together lengths $\geq Y$). $S$ is maximized to be $NY^0.5$ when we have trees of size $Y^0.5$. Thus, such an algorithm runs in $O(NY^1.5)$. We can simply use a data structure such as a set to make sure we only loop over values of $j$ for each tree that has a path of such length.

Finally, we can incorporate the ordering of trees we visit very simply. For a given combination of $K$ paths (one per tree) we can visit the trees in $K!$ orders, and choose $2^K$ options of how we connect adjacent paths. However, this overcounts by a factor of $2K$ (because of circular rotations and reverse direction being equivalent), so we can simply multiply the sum of all path combinations that have length $\geq Y$ by $(N-1)! \times 2^{K-1}$.

A modified version of Benjamin Qi's solution is below:


#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<int, int> pi;
typedef vector<int> vi;
typedef vector<pi> vpi;

#define mp make_pair
#define pb push_back
#define f first
#define s second

const int MOD = 1000000007;
const int MX = 1501;
namespace modOp {
int ad(int a, int b, int mod = MOD) { return (a+b)%mod; }
int sub(int a, int b, int mod = MOD) { return (a-b+mod)%mod; }
int mul(int a, int b, int mod = MOD) { return (ll)a*b%mod; }
int MUL(int& a, int b, int mod = MOD) { return a = mul(a,b,mod); }
}

using namespace modOp;

pi operator+(const pi& l, const pi& r) {
}

pi operator+=(pi& l, const pi& r) {
return l=l+r;
}

pi comb(pi a, pi b) {
}

int N,M,X,Y,K;
bool visit[MX];
vi dist, comp;
pi res, tmp;

void dfs1(int x) {
if (visit[x]) return;
visit[x] = 1;
comp.pb(x);
for(auto t : adj[x]){
dfs1(t.f);
}
}

void dfs2(int x, int p, int ori, int d = 0) {
for(auto t : adj[x]){
if(t.f != p){
if(ori < t.f){
dist.pb(d+t.s);
}
dfs2(t.f,x,ori,d+t.s);
}
}
}

int main() {
ifstream in("mooriokart.in");
ofstream out("mooriokart.out");
in >> N >> M >> X >> Y;
K = N-M;
for(int i = 0; i<M; i++) {
int A,B,D;
in >> A >> B >> D;
}
res[min(K*X,Y)] = {K*X,1};
for(int i = 1; i<=N; i++){
if (!visit[i]) {
comp.clear();
dfs1(i);
dist.clear();
for(auto j : comp){
dfs2(j,-1,j);
}
map<int,pi> m;
for(auto j : dist){
m[min(j,Y)] += mp(j,1);
}
for(int j = 0; j<=Y; j++){
tmp[j] = {0,0};
}
for(auto k : m){
for(int j = 0; j<=Y; j++){
tmp[min(j+k.f,Y)] += comb(res[j],k.s);
}
}
for(int j = 0; j<=Y; j++){
res[j] = tmp[j];
}
}
}
for(int i = 0; i<K-1; i++){
MUL(tmp[Y].f,2);
}
for(int i = 1; i<K; i++){
MUL(tmp[Y].f,i);
}
out << tmp[Y].f << endl;
}