题目描述

现在你面前有一棵n个节点的树（全连通无环图）。树上的边只有2种颜色，红色或者黑色。现在还给你一个整数k，考虑下面这个k个节点的序列[a1, a2, …, ak]。
[a1, a2, …, ak]如果是”好序列“当且仅当满足下面的条件：
1. 我们要走一条从a1开始到ak结束的路径。
2. 从a1开始，到a2走一条a1到a2的最短路。然后从a2开始，继续走一条到a3的最短路，以此类推，最终到a(k-1)和ak。
3. 走的路径中至少包含一条黑色的边。

输入描述

第一行是2个整数n和k，其中(2 <= n <= 10^5, 2 <= k <= 100)，n表示树的节点个数，k表示序列的长度。

下面n-1行，每行包含3个整数，u[i], v[i], w[i]，其中1 <= u[i], v[i] <= n, w[i] = 0或1。u[i], v[i]表示这两个节点之间有一条边，w[i]表示这条边的颜色，其中0表示红色，1表示黑色。

输出描述

输出所有“好序列”的个数模(10^9+7)

示例1

输入

4 4
1 2 1
2 3 1
3 4 1

输出

252

说明

这个例子中，所有序列一共有4^4 = 256个，其中不是好序列的只有4个：

[1, 1, 1, 1]

[2, 2, 2, 2]

[3, 3, 3, 3]

[4, 4, 4, 4]

示例2

输入

4 6
1 2 0
1 3 0
1 4 0

输出

0

示例3

输入

3 5
1 2 1
2 3 0

输出

210

并查集 + 快速幂

面前有一棵n个节点的树（全连通无环图）, 说明去掉黑边， 
就是几个互不连通的连通块(假设两个, 每个连通块点数分别为cnt1, cnt2)。
答案就是n^k - (cnt1)^k - (cnt2)^k, 因为n过大需要使用快速幂, 当然答案不为负, 加上mod一直到变为正数即可。

C++ 代码

#include <iostream>

using namespace std;
const int N = 100010, MOD = 1e9 + 7;
int n, k;
int p[N];
int siz[N];
bool st[N];

long long qmi(int a, int b)
{
    long long res = 1;
    while(b)
    {
        if(b & 1) res = res * 1ll * a % MOD;

        a = a * 1ll * a % MOD;

        b >>= 1;
    }
    return res;
}

int find(int x)
{
    if(p[x] != x) p[x] = find(p[x]);
    return p[x];
}

int main()
{
    cin >> n >> k;
    for(int i = 1; i <= n; i ++)
    {
        p[i] = i;
        siz[i] = 1;
    }

    int a, b, c;
    while(cin >> a >> b >> c)
    {
        if(c == 0)
        {
            a = find(a);
            b = find(b);
            if(a != b)
            {
                p[a] = b;
                siz[b] += siz[a];
            }
        }
    }


    long long res = 0;
    for(int i = 1; i <= n; i ++)
    {
        if(!st[find(i)])
            res += qmi(siz[find(i)], k), st[find(i)] = true;
    }

    // 因为可能为负
    res = qmi(n, k) - res;
    while(res < 0)
    {
        res += MOD;
    }

    cout << res % MOD << endl;

    return 0;
}