题目链接

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

思路

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

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

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

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

代码

#include <bits/stdc++.h>
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;
}