题目链接：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代码：
代码语言：javascript复制#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("%lldn", ans);
return 0;
}
