Tạo Cây
Xem PDF
Điểm:
2300 (p)
Thời gian:
1.0s
Bộ nhớ:
512M
Input:
bàn phím
Output:
màn hình
Minh Đức sau khi tỏ tình thất bại đã trở thành \(1\) sadboiz chính hiệu, anh ta lúc nào cũng như \(1\) người thất thần. Để anh ta mau chóng quên đi "người xém trở thành người yêu của _minhduc nhưng không thành" thì thầy Tiến đã ra \(1\) đề bài ngắn gọn như sau:
- Bạn có một cái cây \(n\) đỉnh và bạn phải điền số \([1..m]\) vô các đỉnh sao cho mọi đỉnh liền kề thì giá trị tuyệt đối hiệu của \(2\) đỉnh \(\ge\) \(k\).
- Yêu cầu bạn hãy đếm số cách điền số vào cây sao cho thoả mãn điều kiện trên
Input
- Dòng đầu tiên gồm \(1\) số nguyên dương \(t\) là số test (\(1 \le t \le 10\)).
- \(t\) bộ test tiếp theo mỗi test theo định dạng sau:
- Dòng đầu gồm \(3\) số nguyên dương \(n,m,k\) (\(1 \le n,k \le 100\),\(1 \le m \le 10^9\)).
- \(n-1\) dòng tiếp gồm \(2\) số nguyên dương \(u,v\) \(-\) có một cạnh nối giữa \(2\) đỉnh \(u,v\)
Output
- Với mỗi bộ test bạn cần in ra trên một dòng: số cách đếm theo yêu cầu đề bài, do kết quả có thể rất lớn nên bạn hãy chia lấy dư cho \(10^9+7\).
Scoring
- Subtask \(1\) (\(20\%\) số điểm): \(1 \le m \le 100\),
- Subtask \(2\) (\(20\%\) số điểm): \(1 \le m \le 10^5\),
- Subtask \(3\) (\(20\%\) số điểm): \(1 \le m \le 10^9\), đỉnh \(1\) nối trực tiếp với \(n-1\) đỉnh khác.
- Subtask \(4\) (\(20\%\) số điểm): \(1 \le m \le 10^9\), đỉnh \(i\) nối với đỉnh \(i+1\), với \(i\) từ \(1\) đến \(n-1\).
- Subtask \(5\) (\(20\%\) số điểm): Không có ràng buộc gì thêm.
Example
Test 1
Input
2
2 2 0
1 2
3 3 2
1 3
1 2Output
4
2
Bình luận
// cre: nnhzzz - Nguyen Ngoc Hung
include <algorithm>
include <bitset>
include <complex>
include <deque>
include <exception>
include <fstream>
include <functional>
include <iomanip>
include <ios>
include <iosfwd>
include <iostream>
include <istream>
include <iterator>
include <limits>
include <list>
include <locale>
include <map>
include <memory>
include <new>
include <numeric>
include <ostream>
include <queue>
include <set>
include <unordered_set>
include <sstream>
include <stack>
include <stdexcept>
include <streambuf>
include <string>
include <typeinfo>
include <utility>
include <valarray>
include <vector>
include <cstring>
include <unordered_map>
include <cmath>
include <cassert>
using namespace std;
define ll long long
define int long long
const int MOD = 1e9+7;
const int maxn = 111;
vector<int> adj[maxn];
int dp[maxn][2LLmaxnmaxn],pre[maxn][2LLmaxnmaxn],fre[maxn][2LLmaxnmaxn];
int tmp[maxn*maxn+maxn],f[maxn];
bool v[maxn];
int n,m,k;
void dfs(int u, int dad){
for(int i = 1; i<=m; ++i){
dp[u][i] = 1;
}
for(auto v:adj[u]){
if(v!=dad){
dfs(v,u);
for(int j = 1; j<=m; ++j){
if(k>0){
dp[u][j] = 1LLdp[u][j](pre[v][max(j-k,0LL)]+fre[v][min(m+1,j+k)])%MOD;
}else{
dp[u][j] = 1LLdp[u][j]pre[v][m]%MOD;
}
}
}
}
for(int i = 1; i<=m; i++){
pre[u][i] = (pre[u][i-1]+dp[u][i])%MOD;
}
for(int i = m; i>0; i--){
fre[u][i] = (fre[u][i+1]+dp[u][i])%MOD;
}
}
void dfs1(int u, int dad){
for(auto v:adj[u]){
if(v!=dad){
dfs1(v,u);
for(int j = 1; j<=nk; j++){
tmp[j] = (tmp[j-1]+dp[v][j])%MOD;
}
for(int j = nk+1; j<=nk+k; j++){
tmp[j] = (tmp[j-1]+dp[v][nk])%MOD;
}
for(int j = 1; j<=nk; j++){
dp[u][j] = 1LLdp[u][j]((f[v]-tmp[j+k-1])%MOD+tmp[max(j-k,0LL)])%MOD;
}
}
}
for(int i = 1; i<=nk; i++){
f[u] = (f[u]+2LLdp[u][i])%MOD;
}
f[u] = (f[u]+1LLdp[u][nk](m-2LLnk))%MOD;
}
signed main(){
#define name "test"
if(fopen(name".inp","r")){
freopen(name".inp","r",stdin);
freopen(name".out","w",stdout);
}
int t; cin >> t;
while(t--){
memset(adj,0,sizeof(adj));
memset(pre,0,sizeof(pre));
memset(fre,0,sizeof(fre));
memset(tmp,0,sizeof(tmp));
memset(f,0,sizeof(f));
cin >> n >> m >> k;
for(int i = 2; i<=n; ++i){
int u,v; cin >> u >> v;
adj[u].push_back(v);
adj[v].push_back(u);
}
if(2LLnk>=m){
dfs(1,0);
cout << pre[1][m];
}else{
if(k==0){
int res = 1;
while(n--){
res = 1LLresm%MOD;
}
cout << res << endl;
continue;
}
for(int i = 1; i<=n; i++){
for(int j = 1; j<=m && j<=2LLnk; j++){
dp[i][j] = 1;
}
}
dfs1(1,0);
cout << (f[1]+MOD)%MOD;
}
cout << endl;
}
return 0;
}