Fişierul intrare/ieşire:	radare.in, radare.out	Sursă	ONI 2011, clasele 11-12
Autor	Andrei Parvu, Bogdan-Cristian Tataroiu	Adăugată de	Gabriel Bitis •gabitzish1
Timp execuţie pe test	0.1 sec	Limită de memorie	65536 kbytes
Scorul tău	N/A	Dificultate	N/A

Vezi solutiile trimise | Statistici

Radare

Odată cu vacanţa de Paşte, Alex s-a hotărât să plece cu maşina la mare. Harta României este modelată ca un arbore (graf conex aciclic neorientat) ce are N noduri, reprezentând oraşele ţării. Este binecunoscut faptul că Alex este vitezoman, de aceea el vrea să se ferească de eventualele radare, care sunt plasate pe muchiile arborelui (pe o muchie se poate afla maxim un radar). Dacă pe o muchie există un radar, atunci Alex nu va risca şi nu va merge pe acea muchie.
Fiecare oraş are un timp de vizitare dat, iar cu toţii ştim că Alex este foarte ocupat, aşadar el nu vrea sa piardă prea mult timp vizitând. Alex pleacă din Gheorgheni (nodul 1, considerat rădăcină) şi doreşte să ştie în câte moduri ar putea fi plasate radarele pe hartă astfel încât timpul total de vizitare al oraşelor accesibile din nodul 1 să fie egal cu P, ştiind că Alex nu va merge pe nicio muchie ce conţine un radar.
Problema aceasta este destul de simplă pentru Alex, aşa că s-a gândit să v-o dea vouă.

Cerinţă

Scrieţi un program care să răspundă problemei lui Alex, adică să determine în câte moduri pot fi plasate radare pe muchii astfel încât timpul total de vizitare al oraşelor accesibile din nodul 1 să fie egal cu P.

Date de intrare

Fişierul de intrare radare.in conţine pe prima linie N şi P, cu semnificaţia din enunţ. Următoarele N-1 linii vor conţine fiecare câte două numere întregi x şi y, însemnând că există o muchie între oraşele x şi y.
Pe ultima linie se vor afla N numere naturale cuprinse între 1 şi P inclusiv, al i-lea dintre acestea reprezentând timpul de vizitare al oraşului i.

Date de ieşire

În fişierul de ieşire radare.out va conţine un singur număr reprezentând răspunsul problemei lui Alex modulo 31333.

Restricţii

• 1 ≤ N ≤ 3.000
• 1 ≤ P ≤ 3.500
• 1 ≤ x, y ≤ N
• 1 ≤ timpul de vizitare al unui oras ≤ P
• dacă un radar este plasat pe o muchie, Alex NU va merge pe acea muchie
• două configuraţii de radare diferă între ele dacă există cel puţin o muchie (a, b) care într-una din configuraţii să conţină un radar, iar în cealaltă nu.
• pentru 30% din teste N ≤ 15
• pentru 50% din teste, timpii de vizitare pentru fiecare oras vor fi 1
• pentru 60% teste, N ≤ 300

Exemplu

Explicaţie

Cele 5 moduri posibile sunt:
1. există radar pe muchia (2,4)
2. sunt radare pe muchiile (2,4), (4,5)
3. sunt radare pe muchiile (2,4), (4,6)
4. sunt radare pe muchiile (2, 4), (4,5), (4,6)
5. sunt radare pe muchiile (1,3), (4,5), (4,6)

Cum se trimit solutii?