SHARE
TWEET

Untitled

a guest Oct 21st, 2019 59 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. typedef long long ll;
  5. typedef double lf;
  6. typedef long double Lf;
  7. typedef pair <int,int> pii;
  8. typedef pair <ll, ll> pll;
  9.  
  10. #define TRACE(x) cerr << #x << "  " << x << endl
  11. #define FOR(i, a, b) for (int i = (a); i < int(b); i++)
  12. #define REP(i, n) FOR(i, 0, n)
  13. #define all(x) (x).begin(), (x).end()
  14. #define _ << " " <<
  15.  
  16. #define fi first
  17. #define sec second
  18. #define mp make_pair
  19. #define pb push_back
  20.  
  21.  
  22. const int mod = 1e9 + 7;
  23. int add(int x, int y) {
  24.   x += y;
  25.   if(x >= mod) return x - mod;
  26.   return x;
  27. }
  28. int sub(int x, int y) {
  29.   x -= y;
  30.   if(x < 0) return x + mod;
  31.   return x;
  32. }
  33. const int MAXN = 2525;
  34.  
  35.  
  36. int sz[MAXN];
  37. vector<int> e[MAXN];
  38.  
  39. int dp[MAXN][MAXN];
  40.  
  41. void dfs(int u, int v) {
  42.   for(auto w: e[v]) {
  43.     if(w != u) dfs(v, w);
  44.     sz[v] += sz[w];
  45.   }
  46.   sz[v] ++;
  47.   for(auto w: e[v]) {
  48.     if(w != u) {
  49.       FOR(k, 1, MAXN) {
  50.         dp[v][k] = add(dp[v][k], dp[w][k - 1]);
  51.       }
  52.     }
  53.   }
  54.   if(sz[v] == 1) FOR(i, 1, MAXN)
  55.     dp[v][i] = i;
  56. }
  57.  
  58. int main() {
  59.   int n, k; cin >> n >> k;
  60.   REP(i, n-1) {
  61.     int u; cin >> u;
  62.     e[1+i].pb(u);
  63.     e[u].pb(1+i);
  64.   }
  65.   dfs(0, 0);
  66.   cout << dp[0][k] _ dp[0][k - 1] << endl;
  67.   cout << sub(dp[0][k], dp[0][k - 1]);
  68.   return 0;
  69. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top