QOJ.ac

QOJ

Limite de temps : 1.5 s Limite de mémoire : 1024 MB Points totaux : 100 Hackable ✓

#14720. 77G-nettverk

Statistiques

Kartet over Meowland kan betraktes som et rotfestet tre med $n$ noder og $n - 1$ kanter, der noder representerer byer og en kant representerer en vei som forbinder to byer. Hovedstaden ligger i roten, node $1$.

Nå ønsker Meowland å installere helt nye basestasjoner for 77G-nettverk i noen byer. For å sikre at hver vei har tilstrekkelig nettverkskvalitet, må minst én av endepunktsbyene for hver vei ha en basestasjon. På grunn av ukjente tekniske problemer har nettverkssystemet imidlertid $m$ feil. Feil $i$ kan beskrives som følger: hvis en basestasjon installeres i by $x_i$, kan ingen byer i undertreet til $x_i$ som har avstand nøyaktig $y_i$ til $x_i$, installere basestasjoner; ellers vil stasjonene forstyrre hverandre og bli ubrukelige.

Vennligst hjelp Meowland med å velge noen byer slik at installering av basestasjoner i disse byene oppfyller alle kravene ovenfor. Hvis det ikke finnes noen gyldig løsning, skriv ut No.

Inndata

Hver testfil inneholder flere testtilfeller. Den første linjen inneholder antallet testtilfeller $T$ ($1 \le T \le 10^3$). Beskrivelsen av testtilfellene følger.

Den første linjen i hvert testtilfelle inneholder et heltall $n$ ($2 \le n \le 2 \times 10^5$), som angir antallet byer.

Den andre linjen inneholder $n - 1$ heltall $f_2, f_3, \dots, f_n$ ($1 \le f_i < i$), der $f_i$ angir forelderen til by $i$.

Den tredje linjen inneholder et heltall $m$ ($0 \le m \le 2 \times 10^5$), som angir antallet feil.

Hver av de neste $m$ linjene inneholder to heltall $x_i$ og $y_i$ ($1 \le x_i, y_i \le n$), som angir den $i$-te feilen. Det kan finnes to identiske feil.

For hver testfil garanteres det at summen av $n$ over alle testtilfeller ikke overstiger $2 \times 10^5$, og at summen av $m$ over alle testtilfeller ikke overstiger $2 \times 10^5$.

Utdata

For hvert testtilfelle, hvis det ikke finnes noen gyldig løsning, skriv ut en linje No.

Ellers, skriv ut tre linjer som representerer løsningen din:

  • På den første linjen skriver du ut Yes.
  • På den andre linjen skriver du ut et heltall $c$, som angir antallet byer du velger.
  • På den tredje linjen skriver du ut $c$ forskjellige heltall, som angir byene du velger.

Hvis det finnes flere gyldige løsninger, kan du skrive ut hvilken som helst av dem. Når du skriver ut løsningen, kan du skrive ut de $c$ byene i hvilken som helst rekkefølge.

Eksempel

Eksempelinndata 1

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

Eksempelutdata 1

Yes
4
5 3 4 1
No
No

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.