链接

[]

题意

给你n个点，n-1个边，无向的。有red和black的。

k表示经过这k个点。可以跨其他点

分析

先算所有的，再减去不符合即可以了。不符合就是都走0的那种

用dfs求联通块并记录该块有多少个点就可以了，看代码吧

代码

#include
    
     using namespace std;#define ll long longconst int N=2e5+10;const ll mod=1e9+7;ll po(ll x,ll y){    ll ba=x,ans=1;    while(y){        if(y&1) ans=(ans*ba)%mod;        ba=(ba*ba)%mod;         y>>=1;    }    return ans;}vector
     
       ve[N];bool vis[N];ll cnt;void dfs(int i){    if(vis[i]) return;    vis[i]=1;    cnt++;    for(int j=0;j
      
       >n>>k;        int u,v,x;        memset(vis,0,sizeof(vis));        for(int i=1;i
       
        >u>>v>>x;            if(x==0)            ve[u].push_back(v),ve[v].push_back(u);        }        ll sum=po(n,k);        for(int i=1;i<=n;i++)        {            cnt=0;            if(!vis[i])             {                dfs(i);              sum-=po(cnt,k);              sum+=mod;              sum%=mod;             }        }        cout<
        
         <