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(并查集+细节)》对你有帮助,请点赞、收藏,并留下你的观点哦!