[cf548]Edgy Trees

Codeforces Round #548 (Div. 2)

C.Edgy Trees

题意

给一个树，树上的边分为黑色或者红色，现在我们定义一个序列[𝑎1,𝑎2,…,𝑎𝑘]

• 我们按照次序经过序列中的每一个点(最短路径)
• 如果进过至少一条黑边，那这个序列就是好的。

题解

至少一条的反义词就是一条都没有，这道题就是找没有黑边的子树。之后答案就是每个子树中的个数的$k$次方。

想着树形dp做，想了很久都没有写出来。

ac代码

#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for(int i=(a);i<(n);i++)
#define per(i,a,n) for(int i=(n-1);i>=(a);i--)
#define fi first
#define se second
typedef pair <int,int> pII;
typedef long long ll;
const int INF = 0x3f3f3f3f;
//head
const ll mod = 1e9+7;
const int maxn = 1e5+10;
int cnt,n,k;
int head[maxn];
struct node{
    int next,to,val;
}G[maxn<<1];
void addedge(int u,int v,int val){
    G[cnt].next = head[u];
    G[cnt].to = v;
    G[cnt].val = val;
    head[u] = cnt++;
}
void init(){
    memset(head,-1,sizeof(head));
    cnt = 0;
}
int vis[maxn];
int t = 0;
void dfs(int u,int fa){
    t ++;
    vis[u] = 1;
    for(int i = head[u];~i;i=G[i].next){
        int v = G[i].to;
        if(v == fa) continue;
        if(vis[v]) continue;
        if(G[i].val == 0)dfs(v,u);
    }
}
ll pow3(ll a,ll b){
    ll res = 1;
    ll x = a;
    while(b){
        if(b&1) res  = res * x % mod;
        b >>= 1;
        x = x*x%mod;
    }
    return res;
}
int main(){
#ifdef LOCAL
    freopen("3.in","r",stdin);
#endif
    init();
    scanf("%d%d",&n,&k);
    rep(i,0,n-1){
        int u,v,val; scanf("%d%d%d",&u,&v,&val);
        addedge(u,v,val); addedge(v,u,val);
    }
    ll ans = pow3(n,k);
    ll last = 0;
    rep(i,1,n+1){
        if(vis[i]==0) dfs(i,-1);
        ll temp = t - last;
        last = t;
        ans = (ans + mod - pow3(temp,k)) % mod;
    }
    printf("%lld\n",ans);
    return 0;
}