4088 - How Long is the Path

Created by Luis Manuel Díaz Barón
Added by ymondelo20 (2018-09-05)
Limits
Total Time: 13000 MS | Test Time: 1000 MS |Memory: 512 MB | Output: 64 MB | Size: 16 KB
Enabled languages
Available in

Description

Given a tree of N (1 <= N <= 10^5) nodes such that each node is either black or red, what is the length of the greatest path containing only red nodes?
Dado un árbol de N (1 <= N <= 10^5) nodos tal que cada nodo es negro o rojo, ¿cuál es la longitud del mayor camino que contiene solo nodos rojos?

Given a tree of N (1 <= N <= 10^5) nodes such that each node is either black or red, what is the length of the greatest path containing only red nodes?

Input specification

On the first line two space-separated integers N (1 <= N <= 10^5) and R (1 <= R <= N), representing the number of nodes and the number of red nodes in the tree. The next line contains R distinct space-separated integers, the indexes of the red nodes. And the next N-1 lines contains two space-separated integers (1 <= A, B <= N) representing the description of one edge between node A and node B.
En la primera línea aparecerán dos enteros separados por espacio: N (1 <= N <= 10^5) y R (1 <= R <= N), que representan el número de nodos y el número de nodos rojos en el árbol respectivamente. La siguiente línea contiene R enteros distintos separados por espacio, representando los índices de los nodos rojos. Las siguientes N-1 líneas contienen cada una dos enteros (1 <= A, B <= N) representando la descripción de una arista entre el nodo A y el nodo B.
On the first line two space-separated integers N (1 <= N <= 10^5) and R (1 <= R <= N), representing the number of nodes and the number of red nodes in the tree. The next line contains R distinct space-separated integers, the indexes of the red nodes. And the next N-1 lines contains two space-separated integers (1 <= A, B <= N) representing the description of one edge between node A and node B.

Output specification

A single integer: the length of the greatest path containing only red nodes.
Un único entero: la longitud del mayor camino que contiene solo nodos rojos.
On the first line two space-separated integers N (1 <= N <= 10^5) and R (1 <= R <= N), representing the number of nodes and the number of red nodes in the tree. The next line contains R distinct space-separated integers, the indexes of the red nodes. And the next N-1 lines contains two space-separated integers (1 <= A, B <= N) representing the description of one edge between node A and node B.

Sample input

10 6
2 3 5 6 7 9
1 2
2 3
2 4
2 5
5 6
1 7
7 8
7 9
9 10

Sample output

4

Hint(s)