Orientacion del Arbol


Submit solution

Points: 100 (partial)
Time limit: 1.0s
Memory limit: 64M

Authors:
Problem types
Allowed languages
Ada, BrainF***, C, C#, C++, Dart, Go, Java, JS, Kotlin, Prolog, Python, Swift, VB

Descripción

Dado un arbol no dirigido con N vertices.

Taea

Encuentra cuantas formas hay de orientar las aristas del arbol tal que el grafo resultante contiene exactamente M vertices que sean vertederos. Un vertice se dice vertedero si no sale ninguna arista de el.

Entrada

La primera linea tendra la cantidad de casos T(1T3) a resolver. Cada caso iniciara con una linea con dos enteros N y M(1N1000,0MN). Luego en las siguientes N1 lineas siguientes se tendran enteros u y v(1u,vN) especificando las aristas del arbol.

Salida

Una linea por cada caso con la cantidad de formas de orientar el arbol y haya M vertices vertedero. Como esta cantidad puede ser muy grande debes imprimirla modulo 109+7.

Ejemplo Entrada

Copy
3
1 0
1 1
5 2
1 2
2 3
3 4
3 5

Salida

Copy
0
1
8

Subtareas

1 - N20, vale 15pts

2 - vi=ui+1, el arbol forma una linea recta a lo largo (N1000), vale 25pts

3 - (N200), vale 30pts

4 - Sin restricciones, vale 30pts


Comments

There are no comments at the moment.