fork download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. typedef long long ll;
  6.  
  7. const ll MOD = 1e9+7;
  8.  
  9. vector <int> G[105];
  10. ll dp[105][1005];
  11. int n,m,p;
  12. bool v[105];
  13.  
  14. void dfs(int u){
  15.     v[u] = 1;
  16.     for(int i = 1; i<=m; ++i){
  17.         dp[u][i] = 1;
  18.     }
  19.     for(int i = 0; i<(int)G[u].size(); ++i){
  20.         if(!v[G[u][i]]){
  21.             int v = G[u][i];
  22.             dfs(v);
  23.             for(int j = 1; j<=m; ++j){
  24.                 ll tot = 0;
  25.                 for(int k = 1; k<=m; ++k){
  26.                     if(abs(j-k)>=p){
  27.                         tot = (tot+dp[v][k])%MOD;
  28.                     }
  29.                 }
  30.                 dp[u][j] = 1LL*dp[u][j]*tot%MOD;
  31.             }
  32.         }
  33.     }
  34.     v[u] = 0;
  35. }
  36.  
  37. int main(){
  38.     int t; cin >> t;
  39.     while(t--){
  40.         memset(G,0,sizeof(G));
  41.         cin >> n >> m >> p;
  42.         for(int i=1;i<n;++i){
  43.             int u,v; cin >> u >> v;
  44.             G[u].push_back(v);
  45.             G[v].push_back(u);
  46.         }
  47.         dfs(1);
  48.         ll ans = 0;
  49.         for(int i = 1; i<=m; ++i){
  50.             ans = (ans+dp[1][i])%MOD;
  51.         }
  52.         cout << ans << endl;
  53.     }
  54.     return 0;
  55. }
Success #stdin #stdout 0.01s 5448KB
comments (?)
stdin
copy 
2
2 2 0
1 2
3 3 2
1 3
1 2
stdout
copy 
4
2
https://ideone.com/jskdXp
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!