Answered step by step
Verified Expert Solution
Link Copied!

Question

1 Approved Answer

The City of Technomania has created a maze game for the residents of the city. The maze is in the form of a tree. The

The City of Technomania has created a maze game for the residents of the city. The maze is in the form of a tree. The residents of the city consider even numbers lucky for them as the name of the city has an even number of duplicates n and a. In the maze, there are N number of posts with each having either a green flag or a red flag . Green flag (G) means you can move ahead in the maze and Red flag (R) means you cannot. There is a pavement between the two posts. There are a total of N-1 pavements between the N posts.
Jess is a curious child and wants to play the maze game. However, she has an interesting take on the game. She wants to know the maximum number of posts she can reach from each post with the condition that she is allowed to change the even number of red flags. It means she is allowed to change 2,4,6,.....etc. number of red flags but not allowed to change 1,3,5,.....etc. number of red flags.
Example:
There are 5 posts in the maze, N =5
There is one red flag (POST 3) and four green flags (POST 1, POST 2, POST 4 and POST 5). The initial map of the maze is as below:
POST 1: If Jess starts her journey from post 1 which is a green flag, she can cover 3 posts at max. The path taken is given below:
Note: Jess cannot convert the red flag of Post 3 to green as she only wants to convert the even number of red flags.
POST 2: Jess can cover the 3 posts: POST 1, POST 2 and POST 4.
POST 3: Post 3 is a red flag and since there is no other red flag in the whole maze, Jess will not be able to convert this red flag into the green flag. As a result, she will not be able to cover any post and since post 3 is also red, it will also not be considered.
POST 4: Jess can cover the 3 posts: POST 1, POST 2 and POST 4.
POST 5: Post 5 is a green flag but Jess cannot reach any other post from here as she has a pavement to Post 3 which is a red flag and cannot be converted to the green flag. The post covered by Jess is 1.
Jess is not good with counting and wants you to help her with the calculations. Help Jess find the maximum number of posts she can reach with the given conditions.
Input Format
The first line of input consists of an integer, N, representing the number of posts in the maze.
Next N-1 lines each consists of two space-separated integers, x and y, representing a pavement between the two posts.
The next line of input consists of a string of length N, where the ith character represents the flag (G or R) at the ith post.
Character G represents the Green Flag and character R represents the Red Flag.
Constraints
1<= N <=4000
1<= x, y <=N
Output Format
Print the maximum number of posts Jess can reach from each of the posts in separate lines. The line number represents the post number in the output.
Sample TestCase 1
Input
5
13
12
24
35
GGRGG
Output
3
3
0
3
1
Explanation
As explained in the example.
Sample TestCase 2
Input
5
12
13
24
35
RGRGR
Output
4
4
4
4
2
Explanation
The initial map of the maze is given below:
POST 1: POST 1 and POST 3 red flags can be converted to the green flags. Jess can cover 4 posts: POST 1, POST 2, POST 3 and POST 4.
POST 2: Jess can cover posts: POST 1, POST 2, POST 3 and POST 4. A similar pavement as from Post 1 is followed.
POST 3: Jess can cover posts: POST 1, POST 2, POST 3 and POST 4. A similar pavement as from Post 1 is followed.
POST 4: Jess can cover posts: POST 1, POST 2, POST 3 and POST 4. A similar pavement as from Post 1 is followed.
POST 5: Jess can cover two posts: POST 5 and POST 3 after converting red flags to green flags. She cannot move further as the Post 1 has a red flag and she can convert only an even number of red flags.

Step by Step Solution

There are 3 Steps involved in it

Step: 1

blur-text-image

Get Instant Access to Expert-Tailored Solutions

See step-by-step solutions with expert insights and AI powered tools for academic success

Step: 2

blur-text-image

Step: 3

blur-text-image

Ace Your Homework with AI

Get the answers you need in no time with our AI-driven, step-by-step assistance

Get Started

Recommended Textbook for

Databases Demystified

Authors: Andrew Oppel

1st Edition

0072253649, 9780072253641

More Books

Students also viewed these Databases questions

Question

Describe strategic succession planning in todays environment.

Answered: 1 week ago

Question

Explain the various elements of a diverse workforce.

Answered: 1 week ago

Question

Describe the strategic planning process.

Answered: 1 week ago