题目链接：https://codeforces.com/contest/1139/problem/C

       题意是给了一棵树，n个点，m条边。让从中选k个点，使得从a1到a2，a2到a3，ak-1到ak的路径中至少经过一条黑色的边，问这样的集合有多少个

       思路就是求他们的组合数，所有的可能就是n^k，假如说像第一个样例那样只有黑色边存在，那么不可行的情况就是下面解释的那样，所以答案就是n^k - n，如果存在红色边的情况，比如说第二个样例，因为2到3连的是红边，那么对于只有这两个点的集合来说，他们的所有情况为2^k，所以答案就是n^k - 2^k - 1(这个1是1 1 1的情况)。那么我们反过来看题中的那个图，连的有红色边的点有6个，那么我们如果让n^k - 6^k肯定是不对的，因为有些点是可以经过黑边到达另一个点的，比如从1到7，那么这样的集合是不应该减的，所以我们要减的应该是只被红边连接的点，而且必须要连通，也就是减去4^k再减去2^k，然后再减去那些剩下的一个集合中只有1个数的情况。

       所以这道题的正解应该是我们将那些连了红边的点建边，然后对于每一个点跑一边dfs，目的是为了找出与当前这个点相连的点有多少个(就是找用红边相连的联通块)，然后减去这个cnt^k就好了。感觉讲的不太好理解，自己看着题上的图想一下就好了。

AC代码：

#include <bits/stdc++.h>
#define ll long long
#define maxn 200005
const ll mod = 1e9 + 7;
using namespace std;
struct Node{
	int to,next,w;
}Edge[maxn];
int head[maxn],num;
ll n,k,cnt;
bool vis[maxn];
map<int,int> ma1,ma2;

ll ppow(ll a, ll b){
	ll sum = 1;
	a %= mod;
	while(b > 0){
		if(b % 2 == 1) sum = (sum * a) % mod;
		b /= 2;
		a = (a * a) % mod;
	}
	return sum % mod;
}

void init(){
	for(int i=0;i<=n;i++) head[i] = -1;
	num = 0;
}

void add(int u,int v,int w){
	Edge[num].to = v;
	Edge[num].w = w;
	Edge[num].next = head[u];
	head[u] = num ++;
}

void dfs(int x){
	cnt ++;
	for(int i=head[x];i!=-1;i=Edge[i].next){
		int to = Edge[i].to;
		if(!vis[to]){
			vis[to] = true;
			dfs(to);
		}
	}
}

int main()
{
  scanf("%lld%lld",&n,&k);
	init();
  for(int i=1;i<n;i++){
    int u, v, w;
    scanf("%d%d%d",&u,&v,&w);
		if(w == 0){
			add(u, v, w);
			add(v, u, w);
		}
  }
  ll cnt2 = 0;
  ll ans = ppow(n, k);
	memset(vis,false,sizeof(vis));
	for(int i=1;i<=n;i++){
		if(vis[i] == false){
			vis[i] = true;
			cnt = 0;
			dfs(i);
			ans = (ans - ppow(cnt, k) + mod) % mod;
		}
	}
  printf("%lld\n", ans);
  return 0;
}