Universal Cup Judging System

Universal Cup

Time Limit: 1.0 s Memory Limit: 1024 MB Total points: 100 Hackable ✓
Statistics

Givet ett orotat träd med $n$ noder ska du tilldela en distinkt vikt till varje nod, så att vikterna bildar en permutation av talen från $1$ till $n$.

För varje tilldelningsschema betraktar vi alla diametrar i trädet (dvs. den längsta enkla vägen i trädet). Bland dessa diametrar väljer vi den som har den lexikografiskt största viktsekvensen (genom att ordna nodernas vikter längs vägen i följd och jämföra dem lexikografiskt).

Ditt mål är att minimera den lexikografiska ordningen för viktsekvensen som motsvarar denna "lexikografiskt största diameter" bland alla möjliga tilldelningsscheman.

Indata

Ett enskilt testfall innehåller flera datagrupper.

Den första raden i indatan är antalet datagrupper $T$ ($1 \le T \le 10^5$), vilket representerar antalet datagrupper i detta testfall.

För varje datagrupp innehåller den första raden ett heltal $n$ ($2 \le n \le 2 \cdot 10^5$) som anger antalet noder.

De följande $n - 1$ raderna innehåller var och en två heltal $u, v$ ($1 \le u, v \le n$), som representerar en kant i trädet.

Det garanteras att över all data gäller $\sum n \le 2 \cdot 10^5$.

Utdata

För varje datamängd, skriv ut en rad med flera heltal som representerar den minsta möjliga lexikografiska ordningen för diametern med den största lexikografiska ordningen.

Exempel

Indata

5
5
1 2
1 3
2 4
2 5
4
1 2
1 3
1 4
6
1 2
1 3
2 4
2 5
3 6
8
1 2
2 3
1 4
2 5
3 6
1 7
7 8
10
1 2
2 3
2 4
4 7
4 8
1 5
5 6
6 9
1 10

Utdata

3 4 5 1
3 4 2
3 4 5 6 1
2 3 4 5 6 1
3 4 5 6 7 8 1

Discussions

About Discussions

The discussion section is only for posting: General Discussions (problem-solving strategies, alternative approaches), and Off-topic conversations.

This is NOT for reporting issues! If you want to report bugs or errors, please use the Issues section below.

Open Discussions 0
No discussions in this category.

Issues

About Issues

If you find any issues with the problem (statement, scoring, time/memory limits, test cases, etc.), you may submit an issue here. A problem moderator will review your issue.

Guidelines:

  1. This is not a place to publish discussions, editorials, or requests to debug your code. Issues are only visible to you and problem moderators.
  2. Do not submit duplicated issues.
  3. Issues must be filed in English or Chinese only.
Active Issues 0
No issues in this category.
Closed/Resolved Issues 0
No issues in this category.