好难的题,队友解释半天才搞懂…
给一棵树,能给叶子染不同的颜色,定义一个节点为happy当且仅当该子树叶子节点(可包括本身)的颜色各不相同,然后求分别有1到n个happy节点的情况下的最小颜色数
反过来想,先考虑n的情况,要n个happy节点,那就是所有叶子都染不同颜色,然后考虑n-1的情况,就去掉一个根节点,那么就变成两棵独立的子树,那只要保证那个叶子节点多的那个子树的叶子染不同的颜色即可,另外的兄弟子树的叶子不管染什么色肯定不会超过这一棵的颜色数,所以其实就是第二大的叶子数的子树,所以答案就是dfs一遍预处理出每个节点对应的子树的叶子节点数,排序输出即可

代码:

#include <bits/stdc++.h>
using namespace std;
const int N=1e5+50;
vector<int> g[N];
int sum[N];
int n,x;
void dfs(int u){
   
    if(g[u].size()==0){
   
        sum[u]=1;
        return;
    }
    int siz=g[u].size();
    for(int i=0;i<siz;i++){
   
        dfs(g[u][i]);
        sum[u]+=sum[g[u][i]];
    }
    return;
}
int main(void){
   
    scanf("%d",&n);
    for(int i=2;i<=n;i++){
   
        scanf("%d",&x);
        g[x].push_back(i);
    }
    dfs(1);
    sort(sum+1,sum+1+n);
    for(int i=1;i<=n;i++){
   
        printf("%d ",sum[i]);
    }
    return 0;
}