C. Edgy Trees Codeforces Round #548 (Div. 2) 【连通块】

一、题面

here

二、分析

这题刚开始没读懂题意，后来明白了，原来就是一个数连通块里点数的问题。首先在建图的时候，只考虑红色路径上的点。为什么呢，因为为了不走红色的快，那么我们可以反着想只走红色的路径，这样把所有的可能数再减去只走红色路径的数就是最终的答案了。这里要注意的是，如果连通块里只有一个点，那么就是K个点都是这个点的情况，根据题意是不满足的，也要减去。

三、AC代码

#include<bits/stdc++.h>

using namespace std;

typedef long long LL;
const int MOD = 1e9 + 7;
const int MAXN = 1e5 + 15;
vector<int> Graph[MAXN];
bool visited[MAXN];
int T, N, K;

LL Pow(LL a, LL b)
{
    LL ans = 1;
    while(b)
    {
        if(b&1)
        {
            ans = ans * a % MOD;
        }
        a = a * a % MOD;
        b >>= 1;
    }
    return ans;
}

void DFS(int v)
{
    if(visited[v])
        return;
    visited[v] = 1;
    T++;
    for(auto &itr:Graph[v])
    {
        DFS(itr);
    }
}



int main()
{
    scanf("%d %d", &N, &K);
    memset(visited, 0, sizeof(visited));
    for(int i = 1; i < N; i++)
    {
        int x, y, c;
        scanf("%d %d %d", &x, &y, &c);
        if(c == 0)
        {

            Graph[x].push_back(y);
            Graph[y].push_back(x);
        }
    }
    LL Ans = 0;
    for(int i = 1; i <= N; i++)
    {
        if(visited[i])
            continue;
        T = 0;
        DFS(i);
        Ans = (Ans + Pow(T, K)) % MOD;
    }
    Ans = (Pow(N, K) - Ans + MOD) % MOD;
    printf("%I64d\n", Ans);
    return 0;
}