C. Edgy Trees
题意：
给你一棵n个结点的联通树，其中有n-1条边，每条边被染了色，为黑色或者红色，给你一个整数k(k>=2)，定义k个顶点的序列[a1,a1...ak]为好序列满足的条件为：1、有一条路径可从a1到达ak（可走重复的点）；2、从a1到a2走的路为最短路，从a2到a3走的路也为最短路，依次类推；3、至少经过一条黑色的边。求好序列有多少个。
思路（dfs, 组合数学）：
由题意可知，这棵树上总的序列数为n的k次方，我们先找到坏的序列数，坏的序列为不经过一条黑边，所以我们把黑边去除，剩下的每个联通图中，任意寻找k个点都不会经过黑色的边，而每个联通图的结点数量为i，则该联通图的坏序列数为i的k次方，用总序列数减去所有坏序列数就是好序列数。
AC代码：
#include<bits/stdc++.h>
using namespace std;
#define IO ios::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define show(x) cout<<x<<endl;
#define show_(x) cout<<x<<" ";
#define showEnd(x) {cout<<x<<endl; return 0;}
#define showxy(x, y) cout<<x<<" "<<y<<endl;
typedef long long ll;
typedef pair<int, int> iip;
typedef pair<ll, ll> llp;
const int MAXN = 200005;
const int INF = 0x3f3f3f3f;
const int MOD = 1e9 + 7;
int i, j, n, k, u, v, x, ans = 0, vis[MAXN] = {0}, step;
vector<int> g[MAXN];
ll quick_pow(ll base, ll pow) {
ll res = 1;
while(pow) {
if(pow & 1 == 1) res = res*base%MOD;//如果是奇数次幂，在一开始的时候多乘了一个base
base = base*base%MOD;
pow >>= 1;
}
return res;
}
void dfs(int s) {
vis[s] = 1;
for(int t : g[s]) {
if(!vis[t]) {
step++;
dfs(t);
}
}
}
int main()
{
cin>>n>>k;
for(i = 0; i < n-1; i++) {
cin>>u>>v>>x;
if(x == 0) {//去除黑边
g[u].push_back(v);
g[v].push_back(u);
}
}
ans = quick_pow(n, k);
for(i = 1; i <= n; i++) {
if(!vis[i]) {
step = 1;
dfs(i);
ans = (ans - quick_pow(step, k) + MOD) % MOD;
}
}
show(ans)
return 0;
}
