给定一个由n个顶点组成的树。树是一个无圈的连通无向图。树的每条边都有它的权重wi。
你的任务是计算满足以下四个条件的不同图形的数量：
Plain Text
图形没有自环和多重边。
图形的边上的权重是整数且不超过S。
图形只有一个最小生成树。
图形的最小生成树是给定的树。
如果两个图的边集不同，则被认为是不同的，考虑到边的权重。
答案可能很大，对998244353取模后输出。
输入：
第一行包含一个整数t（1≤t≤104），表示测试用例的数量。
每个测试用例的第一行包含两个整数n和S（2≤n≤2⋅105，1≤S≤109），表示顶点的数量和权重的上界。
接下来的n-1行描述了树的边，第i行包含三个整数ui，vi和wi（1≤ui,vi≤n，ui≠vi，1≤wi≤S），表示一条权重为wi的边。
保证所有测试用例中n的总和不超过2⋅105。
输出：
对每个测试用例，输出满足条件的不同图形的数量，对998244353取模后输出。
Example
Input
Copy
4
2 5
1 2 4
4 5
1 2 2
2 3 4
3 4 3
5 6
1 2 3
1 3 2
3 4 6
3 5 1
10 200
1 2 3
2 3 33
3 4 200
1 5 132
5 6 1
5 7 29
7 8 187
7 9 20
7 10 4
Output
Copy
1 8 80 650867886
题解:
既然是最小生成树,想想与最小生成树有关的算法,kruskal利用并查集,每次链接两个不在一个集合里面的点,最终使得整个图联通
假设我们现在有两个未在一个集合的集合s1,s2,最多需要s1*s2 - 1条边链接,为啥减一,因为不能有重边,这些边的取值范围x是多少,应该是w < x <= s
每条边有s - w种情况,但是我们也可以啥也不连,所以加一种情况为s - w + 1
每条边都可以这样
情况数为,(s - w + 1)^(s1*s2 - 1)种情况,每次链接两个不相连的集合,都会是这样,所以相乘
#include<bits/stdc++.h>
using namespace std;
#define int long long
struct node
{
int x,y,w;
}a[200040];
bool cmp(node a,node b)
{
return a.w < b.w;
}
int f[200040],d[200043];
int find(int x)
{
if(f[x] == x)
return f[x];
return f[x] = find(f[x]);
}
int mod = 998244353;
int qpow(int x,int p)
{
int ans = 1;
while(p)
{
if(p&1)
ans = ans*x%mod;
x = x*x%mod;
p /= 2;
}
return ans;
}
void solve()
{
int n,s;
cin >> n >> s;
for(int i = 1;i < n;i++)
{
int x,y,w;
cin >> x >> y >> w;
a[i] = {x,y,w};
}
for(int i = 1;i <= n;i++)
{
f[i] = i;
d[i] = 1;
}
sort(a + 1,a + n,cmp);
int ans = 1;
for(int i = 1;i < n;i++)
{
int x = find(a[i].x);
int y = find(a[i].y);
ans = ans*qpow(s - a[i].w + 1,d[x]*d[y] - 1)%mod;
f[y] = x;
d[x] += d[y];
}
cout << ans <<"\n";
}
signed main()
{
int t = 1;
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin >> t;
while(t--)
{
solve();
}
}