Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <cstdio>
- #include <vector>
- #include <set>
- #include <utility>
- #include <algorithm>
- using namespace std;
- const int MAXN = 50100;
- const int MAXK = 501;
- int n, k;
- vector<int> v[MAXN];
- int a, b;
- long long dp[MAXN][MAXK];
- int p[MAXN];
- bool vis[MAXN];
- long long res;
- void go(int u, int anc = -1) {
- vis[u] = true;
- p[u] = anc;
- for (int i = 0; i < (int)v[u].size(); i++) {
- if (!vis[v[u][i]]) {
- go(v[u][i], u);
- for (int j = 0; j < k; j++) {
- dp[u][j + 1] += dp[v[u][i]][j];
- }
- }
- }
- dp[u][0] = 1;
- return;
- }
- long long calc(int u) {
- long long ans = 0;
- for (int i = 0; i < (int)v[u].size(); i++) {
- if (v[u][i] == p[u])
- continue;
- for (int j = 1; j < k; j++) {
- ans += dp[v[u][i]][j - 1] * (dp[u][k - j] - dp[v[u][i]][k - j - 1]);
- }
- }
- //cerr << dp[u][k] << " ";
- ans >>= 1;
- return (ans + dp[u][k]);
- }
- int main() {
- //freopen("input.txt", "r", stdin);
- //freopen("output.txt", "w", stdout);
- scanf("%d%d", &n, &k);
- for (int i = 0; i < n - 1; i++) {
- scanf("%d%d", &a, &b);
- a--, b--;
- v[a].push_back(b);
- v[b].push_back(a);
- }
- go(0);
- for (int i = 0; i < n; i++) {
- //cerr << calc(i) << " ";
- res += calc(i);
- }
- cout << res << endl;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement