Pfadsumme vom Wurzelknoten
Du hast einen Baum mit
n Knoten, wobei der i-te Knoten den Wert () besitzt. Deine Aufgabe ist es, die Anzahl der Pfade im Baum zu bestimmen, die am Wurzelknoten beginnen und deren Summe einem gegebenen Wert s entspricht.Eingabe
Die erste Zeile enthält zwei durch ein Leerzeichen getrennte ganze Zahlen:
n und s (). Diese repräsentieren die Anzahl der Knoten im Baum sowie den Zielwert für die Summe.
Die zweite Zeile enthält n durch Leerzeichen getrennte ganze Zahlen bis (), welche die den Knoten zugewiesenen Werte darstellen.
Die folgenden n-1 Zeilen beschreiben die Kanten des Baumes: Jede Zeile enthält zwei durch ein Leerzeichen getrennte ganze Zahlen a und b (1 ≤ a, b ≤ n), die angeben, dass zwischen den Knoten a und b eine Kante existiert. Es ist garantiert, dass diese Kanten einen gültigen Baum bilden.Ausgabe
Gib eine einzelne ganze Zahl aus, die angibt, wie viele Pfade im Baum am Wurzelknoten starten und eine Summe ergeben, die dem Wert
s entspricht.Beispiele
Eingabe | Ausgabe |
5 6
1 2 3 4 5
1 2
2 3
1 5
5 4 | 2 |
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB