Vértices agrupados#13108

Vértices agrupados

3 segundos
256 megabytes

Se te da un árbol con vértices numerados de a . La distancia entre dos vértices es el número de aristas en el camino simple entre ellos.

Un conjunto no vacío de vértices se llama conexo si para cada dos vértices de todos los vértices del camino simple entre ellos también pertenecen a .

Para cada desde hasta , halla el tamaño máximo de un conjunto conexo tal que la distancia entre cualesquiera dos vértices de sea a lo sumo .

Entrada

La primera línea contiene un único entero (1 \le t \le 5000) — el número de casos de prueba.

La primera línea de cada caso de prueba contiene un entero (1 \le n \le 5000) — el número de vértices. Cada una de las siguientes n - 1 líneas contiene dos enteros y (1 \le u, v \le n, u \ne v) — una arista entre los vértices y . Se garantiza que las aristas forman un árbol.

La suma de sobre todos los casos de prueba no excede .

Salida

Para cada caso de prueba imprime una línea con enteros: el -ésimo de ellos debe ser el tamaño máximo de un conjunto conexo de vértices en el que la distancia entre cualesquiera dos vértices sea a lo sumo .

Ejemplos

Ejemplo 1

Loading
Loading

Nota

En el primer caso de prueba el árbol tiene vértices: el vértice es adyacente a , y , y el vértice es adyacente a , y .

  • Para x = 1 la respuesta es , por ejemplo S = \{1, 3\}.

  • Para x = 2 la respuesta es , por ejemplo S = \{1, 3, 4, 5\}.

  • Para x = 3 la respuesta es , por ejemplo S = \{1, 3, 4, 5, 7\}: las mayores distancias son entre y y entre y , y son iguales a .

  • Para x \ge 4 la respuesta es , ya que el conjunto de todos los vértices tiene distancia máxima .

En el segundo caso de prueba el árbol consta de un solo vértice, por lo que la respuesta es .

En el tercer caso de prueba el árbol es la cadena 1 - 2 - 3 - 4. Un conjunto conexo de vértices de una cadena tiene distancia máxima k - 1, por lo que las respuestas para x = 1, 2, 3, 4 son 2, 3, 4, 4.