传送门
题目大意：给你一棵树，有黑边和紫边，一种k个元素的集合，a1到a2走最短路径.....只要经过黑边那就是好的，问有多少个这种集合。
解题思路：不考虑紫边黑边，就k个元素的集合，那有n^k个。考虑到如果那个集合都是一个全是紫边联通块里的元素，那如何也是不可能走到黑边的，或者是只和黑边连接的点，这也算是一个联通块。那只要把总共的减去这些不合法的，那就是正确的了。减去每个不合法联通块的个数的k次方即可(就是集合元素全在这个联通块中选)。所以合并的时候，只将紫边的两段合并即可。
#include<bits/stdc++.h>#define il inline#define pb push_back#define fi first#define se second#define ms(_data,v) memset(_data,v,sizeof(_data))using namespace std;typedef long long ll;const ll inf=0x3f3f3f3f;const ll mod=1e9+7;const int maxn=1e5+7;int n,k,fa[maxn];bool vis[maxn];map<ll,ll> mp;void init(ll n){for(int i=1;i<=n;++i)fa[i]=i;}ll find(ll x){if(fa[x]==x)return fa[x];else return fa[x]=find(fa[x]);}void unite(ll x,ll y){x=find(x),y=find(y);if(x==y)return;else fa[x]=y;}ll mpow(ll x,ll n){ll ans=1;while(n){if(n&1)ans=(ans*x)%mod;x=(x*x)%mod;n>>=1;}return ans%mod;}int main(){std::ios::sync_with_stdio(0);cin>>n>>k;init(n);int x,y,z;for(int i=1;i<=n-1;++i){cin>>x>>y>>z;if(!z)unite(x,y);}for(int i=1;i<=n;++i)mp[find(i)]++;ll ans=mpow(n,k);for(auto it=mp.begin();it!=mp.end();++it){ans=(ans+mod-mpow(it->se,k))%mod;}cout<<ans<<endl;return 0;}
如果觉得《(CodeForce) C. Edgy Trees (并查集)》对你有帮助，请点赞、收藏，并留下你的观点哦！
