Counting Paths.


Submit solution

Points: 100 (partial)
Time limit: 2.0s
Memory limit: 512M

Author:
Problem type

Se le proporciona un árbol compuesto por n nodos y m rutas.

Su tarea consiste en calcular, para cada nodo, el número de rutas que lo contienen.

Entrada

  • La primera línea de entrada contiene los enteros n y m: el número de nodos y rutas. Los nodos se numeran 1,2,\ldots,n.
  • Luego, hay n-1 líneas que describen las aristas. Cada línea contiene dos enteros a y b: existe una arista entre los nodos a y b.
  • Finalmente, hay m líneas que describen las rutas. Cada línea contiene dos enteros a y b: existe una ruta entre los nodos a y b.

Salida

Imprima n enteros: para cada nodo 1,2,\ldots,n, el número de rutas que contienen ese nodo.

Restricciones

  • 1 \leq n, m \leq 2 \cdot 10^5
  • 1 \leq a,b \leq n

Ejemplo de Entrada

5 3
1 2
1 3
3 4
3 5
1 3
2 5
1 4

Ejemplo de Salida

3 1 3 1 1

Comments

There are no comments at the moment.