Ideone.com

download

copy

#include <bits/stdc++.h>
// #include "testlib.h"  
using namespace std ;
 
#define ft first
#define sd second
#define pb push_back
#define all(x) x.begin(),x.end()
 
#define ll long long int
#define vi vector<int>
#define vii vector<pair<int,int> >
#define pii pair<int,int>
#define plii pair<pair<ll, int>, int>
#define piii pair<pii, int>
#define viii vector<pair<pii, int> >
#define vl vector<ll>
#define vll vector<pair<ll,ll> >
#define pll pair<ll,ll>
#define pli pair<ll,int>
#define mp make_pair
#define ms(x, v) memset(x, v, sizeof x)
 
#define sc1(x) scanf("%d",&x)
#define sc2(x,y) scanf("%d%d",&x,&y)
#define sc3(x,y,z) scanf("%d%d%d",&x,&y,&z)
 
#define scll1(x) scanf("%lld",&x)
#define scll2(x,y) scanf("%lld%lld",&x,&y)
#define scll3(x,y,z) scanf("%lld%lld%lld",&x,&y,&z)
 
#define pr1(x) printf("%d\n",x)
#define pr2(x,y) printf("%d %d\n",x,y)
#define pr3(x,y,z) printf("%d %d %d\n",x,y,z)
 
#define prll1(x) printf("%lld\n",x)
#define prll2(x,y) printf("%lld %lld\n",x,y)
#define prll3(x,y,z) printf("%lld %lld %lld\n",x,y,z)
 
#define pr_vec(v) for(int i=0;i<v.size();i++) cout << v[i] << " " ;
 
#define f_in(st) freopen(st,"r",stdin)
#define f_out(st) freopen(st,"w",stdout)
 
#define fr(i, a, b) for(i=a; i<=b; i++)
#define fb(i, a, b) for(i=a; i>=b; i--)
#define ASST(x, l, r) assert( x <= r && x >= l )
 
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
 
const int mod = 1e9 + 7;
 
int ADD(int a, int b, int m = mod) {
    int s = a;
    s += b;
    if( s >= m )
      s -= m;
    return s;
}
 
int MUL(int a, int b, int m = mod) {
    return (1LL * a * b % m);
}
 
int power(int a, int b, int m = mod) {
    int res = 1;
    while( b ) {
        if( b & 1 ) {
            res = 1LL * res * a % m;
        }
        a = 1LL * a * a % m;
        b /= 2;
    }
    return res;
}
 
ll nC2(ll x) {
    return ( x * ( x - 1 ) / 2 );
}
 
const int maxn = 100 + 5;
const int maxm = 20000 + 10;
 
int dp[ maxn ][ maxm ];
int n, m, k;
vi adj[ maxn ];
 
void netural(int &x) {
	if( x >= mod )
		x -= mod;
	if( x < 0 ) 
		x += mod;
}
 
void brute(int u, int p = 0) {
 
	for( auto it: adj[u] )
		if( it != p ) 
			brute( it, u );
 
	int i; fr(i, 1, m) dp[u][i] = 1;
	fr(i, 1, m) {
		for( auto it: adj[u] ) {
			if( it != p ) {
				int val = 0;
				val += dp[it][max(0, i - k)];
				netural( val );
				if( i + k <= m ) {
					val += (dp[it][m] - dp[it][i+k-1]);
					netural( val );
				}
				if( k == 0 ) {
					val -= dp[it][i] - dp[it][i-1]; 
					netural( val );
				}
				dp[u][i] = 1LL * val * dp[u][i] % mod;
			}
		}
		dp[u][i] += dp[u][i-1];
		netural( dp[u][i] );
	}
}
 
 
const int L1 = 19801;
const int L2 = 9900;
 
int val;
void left(int i, int u, int it) {
	int cnt, v;
	cnt = max(0, i - k);
	if( cnt == 0 ) return;
	if( cnt <= L2 ) {
		val += dp[it][cnt];
	} else {
		val += dp[it][L2];
		netural( val );
		cnt -= L2;
		v = dp[it][L2+1] - dp[it][L2];
		netural( v );
		if( cnt <= m - 2 * L2) {
			val += 1LL * cnt * v % mod;
		} else {
			val += 1LL * (m - 2 * L2) * v % mod;
			netural( val );
			cnt -= (m - 2 * L2);
			val += dp[it][L2+1+cnt] - dp[it][L2+1];
		}
	}
	netural( val );
}
 
void right(int i, int u, int it) {
	int cnt, v;
	cnt = max(0, m - (i+k) + 1);
	if( cnt == 0 ) return;
	if( cnt <= L2 ) {
		val += dp[it][L1] - dp[it][L1-cnt];
	} else {
		val += dp[it][L1] - dp[it][L1-L2];
		netural( val );
		cnt -= L2;
		v = dp[it][L2+1] - dp[it][L2];
		netural( v );
		if( cnt <= m - 2 * L2 ) 
			val += 1LL * cnt * v % mod;
		else {
			val += 1LL * (m - 2 * L2) * v % mod;
			netural( val );
			cnt -= (m - 2 * L2);
			val += dp[it][L2] - dp[it][L2-cnt];
		}
	}
	netural( val );
} 
 
void optimise(int u, int p = 0) {
 
	for( auto it: adj[u] )
		if( it != p ) 
			optimise( it, u );
 
	int i, j; fr(j, 1, L1) dp[u][j] = 1;
	fr(j, 1, L1) {
		if( j > L2+1 )
			i = m - (L1 - j);
		else
			i = j; 
		for( auto it: adj[u] ) {
			if( it != p ) {
				val = 0;
				left(i, u, it);
				right(i, u, it);
				if( k == 0 ) {
					val -= dp[it][j] - dp[it][j-1]; 
					netural( val );
				}
				dp[u][j] = 1LL * dp[u][j] * val % mod;
			}
		}
		dp[u][j] += dp[u][j-1];
		netural( dp[u][j] );
	}
}
 
void solve() {
	cin >> n >> m >> k;
	int i, j;
	fr(i, 1, n-1) {
		int u, v; 
		cin >> u >> v;
		adj[u].pb( v );
		adj[v].pb( u );
	}
 
	if(m >= L1) {
		optimise( 1, 0 );
		int ans = 0, v;
		ans += dp[1][L2];
		netural( ans );
		v = dp[1][L2+1] - dp[1][L2];
		netural( v );
		ans += 1LL * (m - 2 * L2) * v % mod;
		netural( ans );
		ans += dp[1][L1] - dp[1][L1-L2];
		netural( ans );
		cout << ans << "\n";
	} else {
		brute( 1, 0 );
		cout << dp[1][m] << "\n";
	}
 
	fr(i, 1, n) {
		fr(j, 1, min(m, 19801)) dp[i][j] = 0;
		adj[i].clear();
	}
}
 
int main() {
	int t; cin >> t;
	while( t-- ) solve();
}

I2luY2x1ZGUgPGJpdHMvc3RkYysrLmg+Ci8vICNpbmNsdWRlICJ0ZXN0bGliLmgiICAKdXNpbmcgbmFtZXNwYWNlIHN0ZCA7CgojZGVmaW5lIGZ0IGZpcnN0CiNkZWZpbmUgc2Qgc2Vjb25kCiNkZWZpbmUgcGIgcHVzaF9iYWNrCiNkZWZpbmUgYWxsKHgpIHguYmVnaW4oKSx4LmVuZCgpCgojZGVmaW5lIGxsIGxvbmcgbG9uZyBpbnQKI2RlZmluZSB2aSB2ZWN0b3I8aW50PgojZGVmaW5lIHZpaSB2ZWN0b3I8cGFpcjxpbnQsaW50PiA+CiNkZWZpbmUgcGlpIHBhaXI8aW50LGludD4KI2RlZmluZSBwbGlpIHBhaXI8cGFpcjxsbCwgaW50PiwgaW50PgojZGVmaW5lIHBpaWkgcGFpcjxwaWksIGludD4KI2RlZmluZSB2aWlpIHZlY3RvcjxwYWlyPHBpaSwgaW50PiA+CiNkZWZpbmUgdmwgdmVjdG9yPGxsPgojZGVmaW5lIHZsbCB2ZWN0b3I8cGFpcjxsbCxsbD4gPgojZGVmaW5lIHBsbCBwYWlyPGxsLGxsPgojZGVmaW5lIHBsaSBwYWlyPGxsLGludD4KI2RlZmluZSBtcCBtYWtlX3BhaXIKI2RlZmluZSBtcyh4LCB2KSBtZW1zZXQoeCwgdiwgc2l6ZW9mIHgpCgojZGVmaW5lIHNjMSh4KSBzY2FuZigiJWQiLCZ4KQojZGVmaW5lIHNjMih4LHkpIHNjYW5mKCIlZCVkIiwmeCwmeSkKI2RlZmluZSBzYzMoeCx5LHopIHNjYW5mKCIlZCVkJWQiLCZ4LCZ5LCZ6KQoKI2RlZmluZSBzY2xsMSh4KSBzY2FuZigiJWxsZCIsJngpCiNkZWZpbmUgc2NsbDIoeCx5KSBzY2FuZigiJWxsZCVsbGQiLCZ4LCZ5KQojZGVmaW5lIHNjbGwzKHgseSx6KSBzY2FuZigiJWxsZCVsbGQlbGxkIiwmeCwmeSwmeikKCiNkZWZpbmUgcHIxKHgpIHByaW50ZigiJWRcbiIseCkKI2RlZmluZSBwcjIoeCx5KSBwcmludGYoIiVkICVkXG4iLHgseSkKI2RlZmluZSBwcjMoeCx5LHopIHByaW50ZigiJWQgJWQgJWRcbiIseCx5LHopCgojZGVmaW5lIHBybGwxKHgpIHByaW50ZigiJWxsZFxuIix4KQojZGVmaW5lIHBybGwyKHgseSkgcHJpbnRmKCIlbGxkICVsbGRcbiIseCx5KQojZGVmaW5lIHBybGwzKHgseSx6KSBwcmludGYoIiVsbGQgJWxsZCAlbGxkXG4iLHgseSx6KQoKI2RlZmluZSBwcl92ZWModikgZm9yKGludCBpPTA7aTx2LnNpemUoKTtpKyspIGNvdXQgPDwgdltpXSA8PCAiICIgOwoKI2RlZmluZSBmX2luKHN0KSBmcmVvcGVuKHN0LCJyIixzdGRpbikKI2RlZmluZSBmX291dChzdCkgZnJlb3BlbihzdCwidyIsc3Rkb3V0KQoKI2RlZmluZSBmcihpLCBhLCBiKSBmb3IoaT1hOyBpPD1iOyBpKyspCiNkZWZpbmUgZmIoaSwgYSwgYikgZm9yKGk9YTsgaT49YjsgaS0tKQojZGVmaW5lIEFTU1QoeCwgbCwgcikgYXNzZXJ0KCB4IDw9IHIgJiYgeCA+PSBsICkKCiNpbmNsdWRlIDxleHQvcGJfZHMvYXNzb2NfY29udGFpbmVyLmhwcD4KI2luY2x1ZGUgPGV4dC9wYl9kcy90cmVlX3BvbGljeS5ocHA+Cgpjb25zdCBpbnQgbW9kID0gMWU5ICsgNzsKCmludCBBREQoaW50IGEsIGludCBiLCBpbnQgbSA9IG1vZCkgewogICAgaW50IHMgPSBhOwogICAgcyArPSBiOwogICAgaWYoIHMgPj0gbSApCiAgICAgIHMgLT0gbTsKICAgIHJldHVybiBzOwp9CgppbnQgTVVMKGludCBhLCBpbnQgYiwgaW50IG0gPSBtb2QpIHsKICAgIHJldHVybiAoMUxMICogYSAqIGIgJSBtKTsKfQoKaW50IHBvd2VyKGludCBhLCBpbnQgYiwgaW50IG0gPSBtb2QpIHsKICAgIGludCByZXMgPSAxOwogICAgd2hpbGUoIGIgKSB7CiAgICAgICAgaWYoIGIgJiAxICkgewogICAgICAgICAgICByZXMgPSAxTEwgKiByZXMgKiBhICUgbTsKICAgICAgICB9CiAgICAgICAgYSA9IDFMTCAqIGEgKiBhICUgbTsKICAgICAgICBiIC89IDI7CiAgICB9CiAgICByZXR1cm4gcmVzOwp9CgpsbCBuQzIobGwgeCkgewogICAgcmV0dXJuICggeCAqICggeCAtIDEgKSAvIDIgKTsKfQoKY29uc3QgaW50IG1heG4gPSAxMDAgKyA1Owpjb25zdCBpbnQgbWF4bSA9IDIwMDAwICsgMTA7CgppbnQgZHBbIG1heG4gXVsgbWF4bSBdOwppbnQgbiwgbSwgazsKdmkgYWRqWyBtYXhuIF07Cgp2b2lkIG5ldHVyYWwoaW50ICZ4KSB7CglpZiggeCA+PSBtb2QgKQoJCXggLT0gbW9kOwoJaWYoIHggPCAwICkgCgkJeCArPSBtb2Q7Cn0KCnZvaWQgYnJ1dGUoaW50IHUsIGludCBwID0gMCkgewoKCWZvciggYXV0byBpdDogYWRqW3VdICkKCQlpZiggaXQgIT0gcCApIAoJCQlicnV0ZSggaXQsIHUgKTsKCQoJaW50IGk7IGZyKGksIDEsIG0pIGRwW3VdW2ldID0gMTsKCWZyKGksIDEsIG0pIHsKCQlmb3IoIGF1dG8gaXQ6IGFkalt1XSApIHsKCQkJaWYoIGl0ICE9IHAgKSB7CgkJCQlpbnQgdmFsID0gMDsKCQkJCXZhbCArPSBkcFtpdF1bbWF4KDAsIGkgLSBrKV07CgkJCQluZXR1cmFsKCB2YWwgKTsKCQkJCWlmKCBpICsgayA8PSBtICkgewoJCQkJCXZhbCArPSAoZHBbaXRdW21dIC0gZHBbaXRdW2kray0xXSk7CgkJCQkJbmV0dXJhbCggdmFsICk7CgkJCQl9CgkJCQlpZiggayA9PSAwICkgewoJCQkJCXZhbCAtPSBkcFtpdF1baV0gLSBkcFtpdF1baS0xXTsgCgkJCQkJbmV0dXJhbCggdmFsICk7CgkJCQl9CgkJCQlkcFt1XVtpXSA9IDFMTCAqIHZhbCAqIGRwW3VdW2ldICUgbW9kOwoJCQl9CgkJfQoJCWRwW3VdW2ldICs9IGRwW3VdW2ktMV07CgkJbmV0dXJhbCggZHBbdV1baV0gKTsKCX0KfQoKCmNvbnN0IGludCBMMSA9IDE5ODAxOwpjb25zdCBpbnQgTDIgPSA5OTAwOwoKaW50IHZhbDsKdm9pZCBsZWZ0KGludCBpLCBpbnQgdSwgaW50IGl0KSB7CglpbnQgY250LCB2OwoJY250ID0gbWF4KDAsIGkgLSBrKTsKCWlmKCBjbnQgPT0gMCApIHJldHVybjsKCWlmKCBjbnQgPD0gTDIgKSB7CgkJdmFsICs9IGRwW2l0XVtjbnRdOwoJfSBlbHNlIHsKCQl2YWwgKz0gZHBbaXRdW0wyXTsKCQluZXR1cmFsKCB2YWwgKTsKCQljbnQgLT0gTDI7CgkJdiA9IGRwW2l0XVtMMisxXSAtIGRwW2l0XVtMMl07CgkJbmV0dXJhbCggdiApOwoJCWlmKCBjbnQgPD0gbSAtIDIgKiBMMikgewoJCQl2YWwgKz0gMUxMICogY250ICogdiAlIG1vZDsKCQl9IGVsc2UgewoJCQl2YWwgKz0gMUxMICogKG0gLSAyICogTDIpICogdiAlIG1vZDsKCQkJbmV0dXJhbCggdmFsICk7CgkJCWNudCAtPSAobSAtIDIgKiBMMik7CgkJCXZhbCArPSBkcFtpdF1bTDIrMStjbnRdIC0gZHBbaXRdW0wyKzFdOwoJCX0KCX0KCW5ldHVyYWwoIHZhbCApOwp9Cgp2b2lkIHJpZ2h0KGludCBpLCBpbnQgdSwgaW50IGl0KSB7CglpbnQgY250LCB2OwoJY250ID0gbWF4KDAsIG0gLSAoaStrKSArIDEpOwoJaWYoIGNudCA9PSAwICkgcmV0dXJuOwoJaWYoIGNudCA8PSBMMiApIHsKCQl2YWwgKz0gZHBbaXRdW0wxXSAtIGRwW2l0XVtMMS1jbnRdOwoJfSBlbHNlIHsKCQl2YWwgKz0gZHBbaXRdW0wxXSAtIGRwW2l0XVtMMS1MMl07CgkJbmV0dXJhbCggdmFsICk7CgkJY250IC09IEwyOwoJCXYgPSBkcFtpdF1bTDIrMV0gLSBkcFtpdF1bTDJdOwoJCW5ldHVyYWwoIHYgKTsKCQlpZiggY250IDw9IG0gLSAyICogTDIgKSAKCQkJdmFsICs9IDFMTCAqIGNudCAqIHYgJSBtb2Q7CgkJZWxzZSB7CgkJCXZhbCArPSAxTEwgKiAobSAtIDIgKiBMMikgKiB2ICUgbW9kOwoJCQluZXR1cmFsKCB2YWwgKTsKCQkJY250IC09IChtIC0gMiAqIEwyKTsKCQkJdmFsICs9IGRwW2l0XVtMMl0gLSBkcFtpdF1bTDItY250XTsKCQl9Cgl9CgluZXR1cmFsKCB2YWwgKTsKfSAKCnZvaWQgb3B0aW1pc2UoaW50IHUsIGludCBwID0gMCkgewoKCWZvciggYXV0byBpdDogYWRqW3VdICkKCQlpZiggaXQgIT0gcCApIAoJCQlvcHRpbWlzZSggaXQsIHUgKTsKCQoJaW50IGksIGo7IGZyKGosIDEsIEwxKSBkcFt1XVtqXSA9IDE7CglmcihqLCAxLCBMMSkgewoJCWlmKCBqID4gTDIrMSApCgkJCWkgPSBtIC0gKEwxIC0gaik7CgkJZWxzZQoJCQlpID0gajsgCgkJZm9yKCBhdXRvIGl0OiBhZGpbdV0gKSB7CgkJCWlmKCBpdCAhPSBwICkgewoJCQkJdmFsID0gMDsKCQkJCWxlZnQoaSwgdSwgaXQpOwoJCQkJcmlnaHQoaSwgdSwgaXQpOwoJCQkJaWYoIGsgPT0gMCApIHsKCQkJCQl2YWwgLT0gZHBbaXRdW2pdIC0gZHBbaXRdW2otMV07IAoJCQkJCW5ldHVyYWwoIHZhbCApOwoJCQkJfQoJCQkJZHBbdV1bal0gPSAxTEwgKiBkcFt1XVtqXSAqIHZhbCAlIG1vZDsKCQkJfQoJCX0KCQlkcFt1XVtqXSArPSBkcFt1XVtqLTFdOwoJCW5ldHVyYWwoIGRwW3VdW2pdICk7Cgl9Cn0KCnZvaWQgc29sdmUoKSB7CgljaW4gPj4gbiA+PiBtID4+IGs7CglpbnQgaSwgajsKCWZyKGksIDEsIG4tMSkgewoJCWludCB1LCB2OyAKCQljaW4gPj4gdSA+PiB2OwoJCWFkalt1XS5wYiggdiApOwoJCWFkalt2XS5wYiggdSApOwoJfQoKCWlmKG0gPj0gTDEpIHsKCQlvcHRpbWlzZSggMSwgMCApOwoJCWludCBhbnMgPSAwLCB2OwoJCWFucyArPSBkcFsxXVtMMl07CgkJbmV0dXJhbCggYW5zICk7CgkJdiA9IGRwWzFdW0wyKzFdIC0gZHBbMV1bTDJdOwoJCW5ldHVyYWwoIHYgKTsKCQlhbnMgKz0gMUxMICogKG0gLSAyICogTDIpICogdiAlIG1vZDsKCQluZXR1cmFsKCBhbnMgKTsKCQlhbnMgKz0gZHBbMV1bTDFdIC0gZHBbMV1bTDEtTDJdOwoJCW5ldHVyYWwoIGFucyApOwoJCWNvdXQgPDwgYW5zIDw8ICJcbiI7Cgl9IGVsc2UgewoJCWJydXRlKCAxLCAwICk7CgkJY291dCA8PCBkcFsxXVttXSA8PCAiXG4iOwoJfQoKCWZyKGksIDEsIG4pIHsKCQlmcihqLCAxLCBtaW4obSwgMTk4MDEpKSBkcFtpXVtqXSA9IDA7CgkJYWRqW2ldLmNsZWFyKCk7Cgl9Cn0KCmludCBtYWluKCkgewoJaW50IHQ7IGNpbiA+PiB0OwoJd2hpbGUoIHQtLSApIHNvbHZlKCk7Cn0K

Runtime error #stdin #stdout 0.01s 11680KB

stdin

copy

Standard input is empty

stdout

copy

https://ideone.com/wSXtIK

language:

C++14 (gcc 8.3)

created:

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!

Discover > Sphere Engine API

Discover > IDE Widget

Choose your language