题目链接

https://codeforces.com/problemset/problem/1857/G

思路

考虑将给出的树的边按照权值从小到大排序，并模拟最小生成树的过程。

因为 k r u s k a l kruskal kruskal算法在每次合并两个连通块的过程中，会浪费掉两个连通块大小乘积 ? 1 -1 ?1条边。

被浪费掉的边，可以选择的权值为 s ? 当前枚举的这条边的权值 + 1 s-当前枚举的这条边的权值+1 s?当前枚举的这条边的权值+1。（因为有不选的情况，所以要 + 1 +1 +1）。

最后，用快速幂维护枚举每条边时可行方案数的乘积即可。

代码

#include 
using namespace std;
#define int long long
typedef long long i64;
const int N = 2e5 + 5, mod = 998244353;

int n, s;
struct Edge
{
	int u, v, w;
	bool operator<(const Edge &x)
	{
		return w < x.w;
	}
};
int qmi(int a, int b, int c)
{
	int res = 1;
	while (b)
	{
		if (b & 1) res = res * a % c;
		b >>= 1;
		a = a * a % c;
	}
	return res;
}
struct DSU
{
	std::vector<int> f, siz;

	DSU() {}
	DSU(int n)
	{
		init(n);
	}

	void init(int n)
	{
		f.resize(n);
		std::iota(f.begin(), f.end(), 0);
		siz.assign(n, 1);
	}

	int find(int x)
	{
		while (x != f[x])
		{
			x = f[x] = f[f[x]];
		}
		return x;
	}

	bool same(int x, int y)
	{
		return find(x) == find(y);
	}

	bool merge(int x, int y)
	{
		x = find(x);
		y = find(y);
		if (x == y)
		{
			return false;
		}
		siz[x] += siz[y];
		f[y] = x;
		return true;
	}

	int size(int x)
	{
		return siz[find(x)];
	}
};
void solve()
{
	cin >> n >> s;
	vector<Edge> edge;
	for (int i = 1, u, v, w; i < n; i++)
	{
		cin >> u >> v >> w;
		edge.push_back({u, v, w});
	}
	DSU dsu(n + 1);
	sort(edge.begin(), edge.end());
	int ans = 1;
	for (int i = 0; i < edge.size(); i++)
	{
		int fx = dsu.find(edge[i].u);
		int fy = dsu.find(edge[i].v);
		int w = edge[i].w;
		ans = ans * qmi(s - w + 1, dsu.siz[fx] * dsu.siz[fy] - 1, mod) % mod;
		dsu.merge(fx, fy);
	}
	cout << ans << endl;
}
signed main()
{
	ios::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);
	int test = 1;
	cin >> test;
	for (int i = 1; i <= test; i++)
	{
		solve();
	}
	return 0;
}