Fişierul intrare/ieşire:wbtree.in, wbtree.outSursăad-hoc
AutorBogdan SitaruAdăugată dearhivedescarc •arhive
Timp execuţie pe test0.2 secLimită de memorie512000 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Wbtree

Cu toţii ştim ce este acela un ciur (adică o sită); putem folosi unul pentru a separa făina grunjoasă de cea fină. Cu toate acestea, în problema de faţă vom încerca să ciuruim nodurile unui arbore.

Nadgob Ciuruitorul are un arbore (graf neorientat conex aciclic) cu N noduri. Nadgob vrea să aleagă o submulţime S de noduri ale arborelui. Pentru a realiza această alegere, el se va aşeza, pe rând, în K noduri distincte ale arborelui. Odată aşezat într-un nod x al arborelui, el poate, de oricâte ori doreşte, să selecteze un nod y şi să „ciuruiască” (adică să adauge la S) toate nodurile z pentru care y se află pe cel mai scurt drum dintre x şi z. Desigur, un nod care este deja în S nu va fi adăugat din nou.

Nadgob se află acum într-o poziţie de nelămurire existenţială. Plin de angoasă, el se întreabă în câte moduri poate alege submulţimea S conform procedurii enunţate anterior (modulo 109 + 7). Două moduri sunt considerate distincte dacă submulţimile rezultate sunt distincte.

Date de intrare

Pe prima linie a fişierului de intrare wbtree.in se vor găsi numerele N şi K.
Urmează N - 1 linii, fiecare conţinând câte o pereche a b ce reprezintă o muchie din arbore.
Pe ultimul rând al inputului se găsesc K numere, indicii nodurilor în care se aşează Nadgob.

Date de ieşire

Pe singura linie a fişierului de ieşire wbtree.out se va afişa răspunsul cerut.

Restricţii

  • 1 ≤ K ≤ N ≤ 105
  • Pentru 7 puncte, 1 ≤ N * K ≤ 20
  • Pentru alte 9 puncte, 1 ≤ N ≤ 20
  • Pentru alte 9 puncte, arborele conţine cel mult un nod de grad mai mare de 1.
  • Pentru alte 10 puncte, arborele nu conţine niciun nod de grad mai mare de 2.
  • Pentru alte 5 puncte, K = 1
  • Pentru alte 7 puncte, K = N
  • Pentru alte 6 puncte, K = 2
  • Pentru alte 7 puncte, 1 ≤ N ≤ 103

Exemple

wbtree.inwbtree.out
3 1
0 1
0 2
0
5
7 4
0 1
0 2
3 0
4 2
3 6
3 5
4 3 1 2
39

Explicaţie pentru primul exemplu.

Nadgob se aşează în nodul 0.

  1. Selectând niciun y, rezultă S = {}.
  2. Selectând y = 0, rezultă S = {0, 1, 2}.
  3. Selectând y = 1, rezultă S = {1}.
  4. Selectând y = 2, rezultă S = {2}.
  5. Selectând y = 1 şi y = 2, rezultă S = {1, 2}.
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?