You are given a tree (a connected undirected graph without cycles) of n vertices. Each of the n−1−1 edges of the tree is colored in either black or red.
You are also given an integer k. Consider sequences of k vertices. Let's call a sequence [a1,a2,…,ak][1,2,…,] good if it satisfies the following criterion:
- We will walk a path (possibly visiting same edge/vertex multiple times) on the tree, starting from a11 and ending at ak.
- Start at a11, then go to a22 using the shortest path between a1 and a2, then go to a3 in a similar way, and so on, until you travel the shortest path between ak−1−1 and ak.
- If you walked over at least one black edge during this process, then the sequence is good.
Consider the tree on the picture. If k=3=3 then the following sequences are good: [1,4,7], [5,5,3] and [2,3,7][2,3,7]. The following sequences are not good: [1,4,6][1,4,6], [5,5,5][5,5,5], [3,7,3]
There are nk sequences of vertices, count how many of them are good. Since this number can be quite large, print it modulo 109+7109+7.
The first line contains two integers n and k (2≤n≤1052≤≤105, 2≤k≤1002≤≤100), the size of the tree and the length of the vertex sequence.
Each of the next n−1lines contains three integers ui, vi and xi (1≤ui,vi≤n1≤,≤, xi∈{0,1}∈{0,1}), where ui and vi denote the endpoints of the corresponding edge and xi is the color of this edge (00 denotes red edge and 11 denotes black edge).
Print the number of good sequences modulo 109+7109+7.
4 4 1 2 1 2 3 1 3 4 1
252
4 6 1 2 0 1 3 0
1 4 0
0
3 5 1 2 1 2 3 0
210
In the first example, all sequences (4444) of length 44 except the following are good:
- [1,1,1,1]
- [2,2,2,2]
- [3,3,3,3]
- [4,4,4,4]
//https://www.luogu.com.cn/problem/CF1139C //dfs解法 //用dfs记录下来一个连通块的节点数,然后用幂运算算出不合法的方案数 #include<bits/stdc++.h> #define ll long long using namespace std; const int N=1e5+10,mod=1e9+7; int n,k,idx; ll res,num; vector<int>mp[N]; bool vis[N]; //快速幂 // ll qpow(ll x,ll y){ // ll ba=x,ans=1; // while(y){ // if(y&1) ans=(ans*ba)%mod; // ba=(ba*ba)%mod; // y>>=1; // } // return ans; // } //普通幂 ll qpow(int x,int cc) { ll ans=1; for(int i=0;i<cc;i++) ans=(ans*x)%mod; return ans; } void dfs(int x) { vis[x]=true; ++idx; for(auto i:mp[x]) if(!vis[i]) dfs(i); } int main() { std::ios::sync_with_stdio(false); cin>>n>>k; for(int i=1;i<n;i++){ int a,b,c; cin>>a>>b>>c; if(c==0) mp[a].push_back(b), mp[b].push_back(a); } res=qpow(n%mod,k)%mod; for(int i=1;i<=n;i++) if(!vis[i]){ idx=0; dfs(i); num=(num+qpow(idx,k))%mod; } cout<<(res-num+mod)%mod; return 0; }
//并查集解法: //用并查集来维护是否合法 #include<bits/stdc++.h> #define ll long long using namespace std; const int N=1e5+10,mod=1e9+7; int p[N],n,k,vis[N],cnt,idx,mp[N]; bool st[N]; ll res,num; int find(int x) { if(p[x]!=x) p[x]=find(p[x]); return p[x]; } ll qpow(int x) { ll ans=1; for(int i=0;i<k;i++) ans=(ans*x)%mod; return ans; } int main() { std::ios::sync_with_stdio(false); cin>>n>>k; for(int i=1;i<=n;i++) p[i]=i; for(int i=1;i<=n;i++){ int a,b,c; cin>>a>>b>>c; if(c==0) p[find(a)]=find(b);//如果是红的就加进去 } res=qpow(n%mod); for(int i=1;i<=n;i++) mp[find(i)]++;//新方法注意,如何找出这个点的连通块数量? //很明显是这样找得到啦,建立一个桶; for(int i=1;i<=n;i++) num=(num+qpow(mp[i]))%mod; cout<<(res-num+mod)%mod<<endl; return 0; }