C. Edgy Trees
思路：
总共有ans = POW(n,k)中可能，然后排出所有不可能的情况，每次序列中全部为红色或者只有一个点
的情况就不用考虑，所以可以用红色边建立连通图，然后枚举每一连通分量的情况tmp，用ans-tmp就是答案。
---------------------------------------分割线---------------------------------------------------------------------------------------------------
当时我就是这么想的，然后答案就是卡在第8的点上，我怎么也没想到还有负数这种情况W(￣_￣)W，
然后看了标程之后发现ans = (ans+MOD)%MOD,就对了，这次也算get到了，下次一定不会犯这样的错误了。
#include<iostream>#include<cstdio>#include<cstring>using namespace std;typedef long long LL;const int maxn = 200200;const LL MOD = 1e9+7;LL fa[maxn]={0},vis[maxn]={0};LL f(LL x){if(fa[x]==0) return x;else return fa[x]=f(fa[x]);}void Merge(LL x,LL y){LL t1 = f(x),t2 = f(y);if(t1!=t2){fa[t2] = t1;}}LL POW(LL a,LL b){LL ret = 1;while(b){if(b&1LL) ret = ret*a%MOD;a = a*a%MOD;b = b/2;}return ret;}int main(void){LL n,k,i,j,x,y,z;scanf("%lld%lld",&n,&k);for(i=0;i<n-1;i++){scanf("%lld%lld%lld",&x,&y,&z);if(z==0) Merge(x,y);}LL ans = POW(n,k)%MOD;for(i=1;i<=n;i++){vis[f(i)]++;}for(i=1;i<=n;i++)if(vis[i]>0){ans = (ans%MOD-POW(vis[i],k)%MOD)%MOD;}printf("%lld\n",(ans+MOD)%MOD);return 0;}
如果觉得《C. Edgy Trees（并查集+细节）》对你有帮助，请点赞、收藏，并留下你的观点哦！
