White path - MarisaOJ: Marisa Online Judge

Consider a tree with

$n$ vertices, where each vertex is assigned either a white or black color. We want to determine the count of vertices, denoted as

$u$ , on the simple path from vertex

$1$ to vertex

$u$ , where the number of white vertices exceeds the number of black vertices. ### Input - The first line contains an integers

$n$ . - The second line contains a binary string of length

$n$ , denoting the color of

$n$ vertices. The

$i^{th}$ character is the color of vertex

$i$ .

$1$ is black and

$0$ is white. - The next

$n - 1$ lines, each line contains two integers

$u,v$ , there is an edge between

$u$ and

$v$ . ### Output - Print the satisfied vertices. ### Constraints -

$1 \le n \le 10^5$ . -

$1 \le u, v \le n$ . ### Example Input:

$4 0110 1 2 2 3 2 4$

Output:

$2$

Topic

Tree

Rating

800

Solution (1)

Solution