CTree

Time limit: 0.6s
Memory limit: 128MB
Input:
Output:

Renumiți pentru admirația lor pentru boabele de cacao, aztecii s-au hotărât să le depoziteze în capitala imperiului. Imperiul Aztec este format din N orașe (numerotate de la 0 la N − 1), legate prin N − 1 drumuri, astfel încât se poate ajunge din orice oraș în altul parcurgând unul sau mai multe drumuri.

Un oraș poate fi numit capitală doar dacă, în urma distrugerii tuturor drumurilor adiacente acestui oraș, orice mulțime conectată (pentru care oricum am alege 2 orașe, se poate ajunge din primul în cel de-al doilea prin drumuri) are cel mult N2\frac{N}{2} orașe.

Arhitectul șef al aztecilor se gândește să schimbe structura drumurilor din imperiu. Astfel, el poate efectua următoarea operație (posibil de mai multe ori): distruge un drum și construiește unul nou, astfel încât imperiul să rămână conectat.
Arhitectul nu știe încă în ce oraș este cel mai sigur să depoziteze boabele, însă ar vrea să găsească pentru fiecare oraș de la 0 la N − 1 care este numărul minim de operații ce trebuiesc efectuate astfel încât acesta poate fi numit capitală. (Aztecii își pot schimba capitala, atât timp cât boabele lor sunt în siguranță)

Date de intrare

Pe prima linie se va găsi T, numărul de scenarii. Urmează apoi T grupe de linii, fiecare descriind câte un scenariu de rezolvat. Pe prima linie a unui scenariu se află N cu semnificația din enunț. Pe următoarele N - 1 linii urmează două numere x și y separate prin spații, avanâd semnificația că există un drum între x și y.

Date de ieșire

Se vor afișa T linii, fiecare formată din N numere separate prin spații, pentru fiecare i de la 0 la N − 1 numărul minim de operații necesare pentru ca orașul i să poată fi numit capitală.

Restricții și precizări

  • 1 ≤ N ≤ 300 000
  • 0Xi,YiN10 ≤ X_i, Y_i ≤ N − 1 pentru 0 ≤ i ≤ N − 2 și XiYiX_i ≠ Y_i.
  • Fie SNS_N suma N-urilor pentru toate scenariile. 1SN300 0001 ≤ S_N ≤ 300 \ 000.
  • 1 ≤ T ≤ 300 000.
  • Se poate observa că pentru o configurație a drumurilor pot exista mai multe orașe ce pot fi capitală în același timp.

Subtask 1 (7 puncte)

  • 1SN101 ≤ S_N ≤ 10

Subtask 2 (14 puncte)

  • 1SN501 ≤ S_N ≤ 50

Subtask 3 (17 puncte)

  • 1SN2001 ≤ S_N ≤ 200

Subtask 4 (21 de puncte)

  • 1SN2 0001 ≤ S_N ≤ 2 \ 000

Subtask 5 (18 puncte)

  • 1SN40 0001 ≤ S_N ≤ 40 \ 000

Subtask 6 (23 de puncte)

  • Fără restricții suplimentare.

Exemplu

stdin

2
3
0 2
0 1
7
1 0
1 2
2 3
3 4
5 1
1 6

stdout

0 1 1
1 0 1 2 2 1 1

Explicații

Pentru primul exemplu:

  • Orașul 0 poate fi numit capitală fără a efectua modificări.
  • Pentru orașul 1, se distruge drumul (0, 2) și se construiește drumul (1, 2).
  • Pentru orașul 2, se distruge drumul (0, 1) și se construiește drumul (1, 2).

Problem info

ID: 93

Editor: liviu

Author:

Source: Lot 2021 Baraj 1 Seniori: Problema 3

Tags:

Lot 2021 Baraj 1 Seniori

Log in or sign up to be able to send submissions!