Bình luận

• 
  

  -10

  PY1ELeTrongNhan    9:57 a.m. 7 Tháng 10, 2023

  // 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;
  }

  Bình luận bị ẩn vì nhiều phản hồi tiêu cực. Nhấp vào đây để mở.