Guest User

Untitled

a guest
Oct 21st, 2019
62
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