Decorate Apple Tree

Topic translation

The main idea of the topic

To give you one $n$ Nodes with $1$ A tree for roots , To give the $n$ Random coloring of nodes , Define a point as a happy node if and only if all points on the subtree of this node have different colors . Find out for $1\sim n$ Each of them $k$, The number of happy knots is greater than or equal to $k$ The minimum number of colors required .

Input format

Number one on the first line $n(1\le n\le 10^5)$, Indicates the number of nodes

The second line $n-1$ Number $p_i$, It means the first one $i$ Parent node of nodes $(1\le p_i<i)$

Output format

a line ,$n$ Number , For $1\sim n$ Each of them $k$, The number of happy nodes is greater than or equal to $k$ The minimum number of colors required for

Examples #1

The sample input #1

3
1 1

Sample output #1

1 1 2

Examples #2

The sample input #2

5
1 1 3 3

Sample output #2

1 1 1 2 3

Can't think of , Notice that the number of leaf nodes in a given tree will be output 1, The last number is in 1 Is the maximum value of the leaf node of the subtree of the root , Then I couldn't think of it .

Caption , The problem can be transformed into how many leaf nodes there are in the subtree rooted at each point , Sorting is the answer .

Don't understand , I know I read others' explanations

Give a tree , Can dye leaves with different colors , Define a node as happy If and only if the leaf node of the subtree ( It can include itself ) The colors are different , Then ask for the difference 1 To n individual happy The minimum number of colors in the case of nodes
In turn to , Think about it first n The situation of , want n individual happy node , That is, all leaves are dyed in different colors , Then consider n-1 The situation of , Just remove a root node , Then it becomes two independent subtrees , Just make sure that the leaves of the subtree with many leaf nodes are dyed with different colors , No matter what color the leaves of other brother trees are dyed, they will not exceed the number of colors of this one , So it is actually the subtree with the second largest number of leaves , So the answer is dfs Preprocess the number of leaf nodes of the subtree corresponding to each node once , Sort the output

（ A question that comes to mind ） How to find 1 ~ n The number of nodes of the largest subtree rooted at each point in . Excavation without filling

How to use tape int As a return value dfs Seeking for u How many leaf nodes does the root subtree have ？

 Two completely equivalent expressions , I always feel that those without return values are easier to write than those with return values .
int dfs(int u,int fa){
    
	bool flag = 1;
	for(int i=h[u];i!=-1;i=ne[i]){
    
		int j = e[i];
		if(e[i]==fa)continue;
		flag = 0;
		cnt[u] += dfs(j,u);
	}
	if(flag){
    
		cnt[u] = 1;
	}
	return cnt[u];
}

void dfs(int u,int fa){
    
	bool flag = 1;
	for(int i=h[u];i!=-1;i=ne[i]){
    
		int j = e[i];
		if(e[i]==fa)continue;
		flag = 0;
		dfs(j,u);
		cnt[u]+=cnt[e[i]];
	}
	if(flag){
    
		cnt[u] = 1;
	}
}