Decorate Apple Tree

直接统计下每个节点有多少叶子节点,排序输出即可.

#include <bits/stdc++.h>
using namespace std;
const int N=1e5+5;
vector<int>v[N];
int dp[N];
void dfs(int u)
{
    if(v[u].size()==0) dp[u]=1;
    for(int i=0;i<v[u].size();i++)
    {
        int x=v[u][i];
        dfs(x);
        dp[u]+=dp[x];
    }
}

int main()
{
    int n;
    scanf("%d",&n);
    for(int i=2;i<=n;i++)
    {
        int x;
        scanf("%d",&x);
        v[x].push_back(i);
    }
    dfs(1);
    sort(dp+1,dp+1+n);
    for(int i=1;i<=n;i++) printf("%d ",dp[i]);
    puts("");
    return 0;
}