Qruplaşdırılmış təpələr#13108

Qruplaşdırılmış təpələr

3 saniyə
256 meqabayt

Sizə -dən -ə qədər nömrələnmiş təpəsi olan ağac verilir. İki təpə arasındakı məsafə onların arasındakı sadə yoldakı tillərin sayıdır.

Boş olmayan təpələr çoxluğu əlaqəli adlanır, əgər -in istənilən iki təpəsi üçün onların arasındakı sadə yolun bütün təpələri də -ə aiddirsə.

-dən -ə qədər hər bir üçün elə əlaqəli çoxluğunun maksimal ölçüsünü tapın ki, -in istənilən iki təpəsi arasındakı məsafə -dən böyük olmasın.

Giriş

Birinci sətirdə bir tam ədəd (1 \le t \le 5000) — test hallarının sayı verilir.

Hər test halının birinci sətrində tam ədəd (1 \le n \le 5000) — təpələrin sayı verilir. Növbəti n - 1 sətrin hər birində iki tam ədəd və (1 \le u, v \le n, u \ne v) — və təpələri arasındakı til verilir. Tillərin ağac əmələ gətirdiyi qarantiya olunur.

Bütün test halları üzrə qiymətlərinin cəmi -i aşmır.

Çıxış

Hər test halı üçün tam ədəddən ibarət bir sətir çap edin: onlardan -incisi elə əlaqəli təpələr çoxluğunun maksimal ölçüsü olmalıdır ki, orada istənilən iki təpə arasındakı məsafə -dən böyük olmasın.

Nümunələr

Nümunə 1

Loading
Loading

Qeyd

Birinci test halında ağacın təpəsi var: təpəsi , və ilə qonşudur, təpəsi isə , və ilə qonşudur.

  • x = 1 üçün cavab -dir, məsələn S = \{1, 3\}.

  • x = 2 üçün cavab -dür, məsələn S = \{1, 3, 4, 5\}.

  • x = 3 üçün cavab -dir, məsələn S = \{1, 3, 4, 5, 7\}: ən böyük məsafələr ilə arasında və ilə arasındadır və onlar -ə bərabərdir.

  • x \ge 4 üçün cavab -dir, çünki bütün təpələr çoxluğunun ən böyük məsafəsi -dür.

İkinci test halında ağac yalnız bir təpədən ibarətdir, buna görə cavab -dir.

Üçüncü test halında ağac 1 - 2 - 3 - 4 zənciridir. Zəncirin təpədən ibarət əlaqəli çoxluğunun ən böyük məsafəsi k - 1-dir, buna görə x = 1, 2, 3, 4 üçün cavablar 2, 3, 4, 4-dür.