Universal Cup Judging System

Universal Cup

Límite de tiempo: 3.0 s Límite de memoria: 2048 MB Puntuación total: 100 Dificultad: [mostrar] Hackeable ✓
Estadísticas

Пигги (бос уақытында Жұлдызаралық байланыс хаттамасы комиссиясын басқарады) күрделі аппараттық мәселеге тап болды. Ағаш құрылымын құрайтын $(n - 1)$ талшықты-оптикалық желімен байланысқан $n$ ретрансляциялық станциядан тұратын ең жаңа коммуникациялық тор ақыры іске қосуға дайын. Алайда жүйеге қуат беру аса сақтықпен жүргізілуі тиіс.

Белсендіру процесі белгілі бір жолдар бойымен лазерлік импульстарды жіберуді қамтиды. Жол ретінде екі станция арасындағы жалғыз қарапайым маршрут анықталады. Комиссия заңгерлерін түні бойы ұйықтатпайтын құбылыс — «Кванттық кері ағын интерференциясының» апатты қаупіне байланысты келесі хаттама қатаң сақталуы керек:

  • Тарату жолдары бірінен соң бірі орнатылуы тиіс.
  • Қуаттың күрт артуын болдырмау үшін, әрбір жаңадан орнатылған жол бұрынғы кез келген жол арқылы белсендірілген станциялар жиынымен ең көбі бір станцияны ғана ортақ пайдалана алады.

Формалды түрде, $S$ — қазіргі уақытта белсендірілген станциялар жиыны болсын. $V(P)$ станциялар жиынынан тұратын кез келген жаңа $P$ жолы үшін $|V(P) \cap S| \le 1$ шарты орындалуы тиіс. Жол бойымен импульс сәтті жіберілгеннен кейін, сол жолдың бойындағы барлық станциялар белсендірілген $S$ жиынының бөлігі болып саналады.

Сіздің миссияңыз (егер оны қабылдауды таңдасаңыз) — бүкіл желідегі әрбір станцияны белсендіру үшін қажетті лазерлік импульстардың ең аз санын анықтау және заң бөлімінің талабын қанағаттандыру үшін осындай жолдар тізбегінің бірін ұсыну.

problem_16337_7ea995da1220bc7e6a98609de7d2cace.png
Алғашқы екі мысал тест жағдайының иллюстрациясы. 2-жағдайда екінші импульс біріншісімен тек $2$-станцияны ғана ортақ пайдаланып, интерференция болмау ережесін қанағаттандыратынына назар аударыңыз.

Кіріс деректер

Бірнеше тест жиынтығы берілген. Кірістің бірінші жолында тест жиынтықтарының санын білдіретін бүтін $T$ ($1 \le T \le 10^4$) саны берілген. Әрбір тест жиынтығы үшін:

Бірінші жолда тордағы станциялар санын білдіретін бүтін $n$ ($2 \le n \le 3 \times 10^5$) саны берілген.

Келесі $(n - 1)$ жолдың $i$-ші жолында $u_i$ мен $v_i$ станциялары арасындағы екі бағытты талшықты-оптикалық желіні сипаттайтын екі бүтін $u_i$ және $v_i$ ($1 \le u_i, v_i \le n, u_i \neq v_i$) сандары берілген.

Желілердің ағаш құрайтынына және барлық тест жиынтықтары бойынша $n$ мәндерінің қосындысы $3 \times 10^5$ шамасынан аспайтынына кепілдік беріледі.

Шығыс деректер

Әрбір тест жиынтығы үшін бірінші жолда жолдардың ең аз $k$ санын шығарыңыз. Одан кейін $k$ жол шығарыңыз, олардың әрқайсысында тізбектегі $i$-ші жолдың шеткі нүктелерін білдіретін екі бүтін $a_i$ және $b_i$ сандары болуы керек. Егер жол бір ғана станциядан тұрса, $a_i$ мен $b_i$ тең болуы мүмкін екенін ескеріңіз.

Егер бірнеше оңтайлы тізбек бар болса, интерференция болмау хаттамасын қатаң сақтайтын кез келгені қабылданады.

Мысал

Кіріс деректер

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

Шығыс деректер

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

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.