Maximum Expectation Value in Secret Meetings

Given a tree with N nodes (numbered 1 through N) where every node has one person, a secret meeting is held by choosing a subset S of nodes such that |S| = j. For any node k (which does not need to be in S), define

$$f(k)=\sum_{p\in S} d(k,p),$$

where \(d(a,b)\) is the distance (i.e. the number of edges) on the tree between nodes \(a\) and \(b\). A node \(k\) is called expectable if \(f(k)\) is minimized over all nodes. In other words, the expectation set for S is

$$M(S)=\{k\in V:\, f(k)=\min_{x\in V} f(x)\}.$$

The expectation value of the meeting is defined as the number of expectable nodes \(|M(S)|\). For each \(j\in [1,N]\), find the maximum possible expectation value over all choices of S with \(|S|=j\>.

Note: It can be proved that if the meeting size j is odd, then the expectable set is always a single node; while if j is even, by optimally choosing the set S along a longest path (i.e. a diameter) of the tree, the expectable set forms a contiguous segment of nodes along that path. In particular, if we denote by \(D\) the number of nodes in a diameter of the tree, then by choosing S as some nodes on this diameter, one may achieve an expectation value of

$$\max\;|M(S)|= \narray{cases} 1, & \text{if } j \text{ is odd or } j > D,\\ D - j + 2, & \text{if } j \text{ is even and } j \le D. \endarray $$

Your task is to compute, for each \(j\) from 1 to \(N\), the maximum possible expectation value.

inputFormat

The first line contains an integer \(N\) (the number of nodes in the tree).\n

Each of the next \(N-1\) lines contains two integers \(u\) and \(v\) indicating there is an undirected edge between nodes \(u\) and \(v\).

outputFormat

Output a single line containing \(N\) space‐separated integers. The j-th integer represents the maximum expectation value (i.e. the maximum number of expectable nodes) for a meeting of \(j\) persons.

sample

4
1 2
1 3
1 4

1 3 1 1