fork download
copy 
  1. // cre: nnhzzz - Nguyen Ngoc Hung
  2.  
  3. #include <algorithm>
  4. #include <bitset>
  5. #include <complex>
  6. #include <deque>
  7. #include <exception>
  8. #include <fstream>
  9. #include <functional>
  10. #include <iomanip>
  11. #include <ios>
  12. #include <iosfwd>
  13. #include <iostream>
  14. #include <istream>
  15. #include <iterator>
  16. #include <limits>
  17. #include <list>
  18. #include <locale>
  19. #include <map>
  20. #include <memory>
  21. #include <new>
  22. #include <numeric>
  23. #include <ostream>
  24. #include <queue>
  25. #include <set>
  26. #include <unordered_set>
  27. #include <sstream>
  28. #include <stack>
  29. #include <stdexcept>
  30. #include <streambuf>
  31. #include <string>
  32. #include <typeinfo>
  33. #include <utility>
  34. #include <valarray>
  35. #include <vector>
  36. #include <cstring>
  37. #include <unordered_map>
  38. #include <cmath>
  39. #include <cassert>
  40.  
  41. using namespace std;
  42.  
  43. #define ll long long
  44. #define int long long
  45.  
  46. const int MOD = 1e9+7;
  47. const int maxn = 111;
  48.  
  49. vector<int> adj[maxn];
  50. int dp[maxn][2LL*maxn*maxn],pre[maxn][2LL*maxn*maxn],fre[maxn][2LL*maxn*maxn];
  51. int tmp[maxn*maxn+maxn],f[maxn];
  52. bool v[maxn];
  53. int n,m,k;
  54.  
  55. void dfs(int u, int dad){
  56.     for(int i = 1; i<=m; ++i){
  57.         dp[u][i] = 1;
  58.     }
  59.     for(auto v:adj[u]){
  60.         if(v!=dad){
  61.             dfs(v,u);
  62.             for(int j = 1; j<=m; ++j){
  63.                 if(k>0){
  64.                     dp[u][j] = 1LL*dp[u][j]*(pre[v][max(j-k,0LL)]+fre[v][min(m+1,j+k)])%MOD;
  65.                 }else{
  66.                     dp[u][j] = 1LL*dp[u][j]*pre[v][m]%MOD;
  67.                 }
  68.             }
  69.         }
  70.     }
  71.     for(int i = 1; i<=m; i++){
  72.         pre[u][i] = (pre[u][i-1]+dp[u][i])%MOD;
  73.     }
  74.     for(int i = m; i>0; i--){
  75.         fre[u][i] = (fre[u][i+1]+dp[u][i])%MOD;
  76.     }
  77. }
  78.  
  79. void dfs1(int u, int dad){
  80.     for(auto v:adj[u]){
  81.         if(v!=dad){
  82.             dfs1(v,u);
  83.             for(int j = 1; j<=n*k; j++){
  84.                 tmp[j] = (tmp[j-1]+dp[v][j])%MOD;
  85.             }
  86.             for(int j = n*k+1; j<=n*k+k; j++){
  87.                 tmp[j] = (tmp[j-1]+dp[v][n*k])%MOD;
  88.             }
  89.             for(int j = 1; j<=n*k; j++){
  90.                 dp[u][j] = 1LL*dp[u][j]*((f[v]-tmp[j+k-1])%MOD+tmp[max(j-k,0LL)])%MOD;
  91.             }
  92.         }
  93.     }
  94.     for(int i = 1; i<=n*k; i++){
  95.         f[u] = (f[u]+2LL*dp[u][i])%MOD;
  96.     }
  97.     f[u] = (f[u]+1LL*dp[u][n*k]*(m-2LL*n*k))%MOD;
  98. }
  99.  
  100. signed main(){
  101.     #define name "test"
  102.     if(fopen(name".inp","r")){
  103.         freopen(name".inp","r",stdin);
  104.         freopen(name".out","w",stdout);
  105.     }
  106.     int t; cin >> t;
  107.     while(t--){
  108.         memset(adj,0,sizeof(adj));
  109.         memset(pre,0,sizeof(pre));
  110.         memset(fre,0,sizeof(fre));
  111.         memset(tmp,0,sizeof(tmp));
  112.         memset(f,0,sizeof(f));
  113.         cin >> n >> m >> k;
  114.         for(int i = 2; i<=n; ++i){
  115.             int u,v; cin >> u >> v;
  116.             adj[u].push_back(v);
  117.             adj[v].push_back(u);
  118.         }
  119.         if(2LL*n*k>=m){
  120.             dfs(1,0);
  121.             cout << pre[1][m];
  122.         }else{
  123.             if(k==0){
  124.                 int res = 1;
  125.                 while(n--){
  126.                     res = 1LL*res*m%MOD;
  127.                 }
  128.                 cout << res << endl;
  129.                 continue;
  130.             }
  131.             for(int i = 1; i<=n; i++){
  132.                 for(int j = 1; j<=m && j<=2LL*n*k; j++){
  133.                     dp[i][j] = 1;
  134.                 }
  135.             }
  136.             dfs1(1,0);
  137.             cout << (f[1]+MOD)%MOD;
  138.         }
  139.         cout << endl;
  140.     }
  141.     return 0;
  142. }
Success #stdin #stdout 0.02s 46300KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0
https://ideone.com/sNg0k3
language:
C++14 (gcc 8.3)
created:
1 year ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!