题意：添加几条线段，使得图仍保持原先的最小生成树
通过画图我们发现，要添加u->v的线段，线段必须大于u->v的路径内的最大值，不然会破坏原先的最小生成树。
那么该怎么维护路径内的最大值呢？
方法：
1.我们对边的大小进行排序，这样当前边一定大于等于之前的边，只要对当前边进行操作就行。
但是这样可能会造成多个集合，那我们可以利用并查集
2.对于两个集合，它们最多能加的边只有siz_l*siz_r-1（因为不能有重边，所以要减一）,那么它们的组合是怎样的？
可以这样想，每条边的选着可以是[S,w），0（不加也是一种选着）,所以对于每条边都可以有S-w+1中可能，一共有siz_l * siz_r-1条边,根据乘法原理，它们总的组合是（S-w+1）^(siz_l * siz_r-1)。
3.两集合合并后记得更改其大小
4.那么总的组合就是这些组合的相乘
点击查看代码
#include<bits/stdc++.h>
using namespace std;
#define LL long long
const int N = 2e5 + 10,mod= 998244353;
int f[N],siz[N];
int find(int x) {
return f[x] == x ? x : f[x] = find(f[x]);
}
void solve() {
LL n, S;
cin >> n >> S;
vector<array<LL, 3>> v(n-1);
for (int i = 0; i < n-1; i++) {
cin >> v[i][0] >> v[i][1] >> v[i][2];
}
//最小生成树
sort(v.begin(), v.end(), [&](array<LL, 3> &a, array<LL, 3> &b) {
return a[2] < b[2];
}
);
auto _pow = [](LL a, LL b) {//快速幂
LL res = 1;
while (b) {
if (b & 1) res = res * a % mod;
a = a * a % mod;
b >>= 1;
}
return res;
};
LL ans = 1;
for (int i = 0; i <= n; i++) f[i] = i,siz[i]=1;//初始化
for (int i = 0; i < n - 1; i++) {
int x = find(v[i][0]);
int y = find(v[i][1]);
if (x != y) {
ans = (ans*_pow(S - v[i][2]+1, 1LL*siz[x] * siz[y] - 1))%mod;
siz[y] += siz[x];//更新集合内的数量
f[x] = y;//合并到y集合
}
}
cout<< ans;
cout << "\n";
}
int main() {
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int t;
cin >> t;
while (t--) {
solve();
}
return 0;
}