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. typedef long long ll;
  44.  
  45. const ll MOD = 1e9+7;
  46. const ll maxn = 1e5+7;
  47.  
  48. vector <int> G[105];
  49. ll dp[105][maxn],pre[105][maxn],fre[105][maxn];
  50. int n,m,p;
  51. bool v[105];
  52.  
  53. void dfs(int u){
  54.     v[u] = 1;
  55.     for(int i = 1; i<=m; ++i){
  56.         dp[u][i] = 1;
  57.     }
  58.     for(int i = 0; i<(int)G[u].size(); ++i){
  59.         if(!v[G[u][i]]){
  60.             int v = G[u][i];
  61.             dfs(v);
  62.             for(int j = 1; j<=m; ++j){
  63.                 if(p>0){
  64.                     dp[u][j] = 1LL*dp[u][j]*(pre[v][max(j-p,0)]+fre[v][min(m+1,j+p)])%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.     v[u] = 0;
  78. }
  79.  
  80. int main(){
  81.     #define name "test"
  82.     if(fopen(name".inp","r")){
  83.         freopen(name".inp","r",stdin);
  84.         freopen(name".out","w",stdout);
  85.     }
  86.     int t; cin >> t;
  87.     while(t--){
  88.         memset(G,0,sizeof(G));
  89.         memset(pre,0,sizeof(pre));
  90.         memset(fre,0,sizeof(fre));
  91.         cin >> n >> m >> p;
  92.         for(int i=1;i<n;++i){
  93.             int u,v; cin >> u >> v;
  94.             G[u].push_back(v);
  95.             G[v].push_back(u);
  96.         }
  97.         dfs(1);
  98.         cout << pre[1][m] << endl;
  99.     }
  100.     return 0;
  101. }
Success #stdin #stdout 0.01s 5472KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/pr1hy3
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!