[cf548]Edgy Trees

Codeforces Round #548 (Div. 2)

C.Edgy Trees

题意

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

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

题解

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

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

ac代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
#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;
}