每个点的子树大小

这道题由于时间卡的太紧，所以不可能每个节点都搜一次，只能记忆化搜索
不难发现一个节点的子树大小等于它的子树的子树大小相加再加1，所以记忆化即可

#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
#define pb push_back
using namespace std;

int cnt[1005];
vector<int> G[1005];

void dfs(int u) {
  cnt[u] = 1;
  for (auto p : G[u]) {
    if (cnt[p]) continue;
    dfs(p);
    cnt[u] += cnt[p];
  }
}

int main() {
  int n;
  cin >> n;
  for (int i = 1; i < n; i++) {
    int x;
    cin >> x;
    G[x].pb(i + 1);
    G[i + 1].pb(x);
  }
  dfs(1);
  for (int i = 1; i <= n; i++) cout << cnt[i] << ' ';
  return 0;
}