Require Help in A graph qn asked in Uber OA

#	User	Rating
1	tourist	3880
2	jiangly	3669
3	ecnerwala	3654
4	Benq	3627
5	orzdevinwang	3612
6	Geothermal	3569
6	cnnfls_csy	3569
8	jqdai0815	3532
9	Radewoosh	3522
10	gyh20	3447

#	User	Contrib.
1	awoo	161
2	maomao90	160
3	adamant	157
4	maroonrk	154
5	-is-this-fft-	148
5	atcoder_official	148
5	SecondThread	148
8	Petr	147
9	TheScrasse	145
9	nor	145

Hey everyone, any help with the following graph qn is very much appreciated.

Problem Statement:

Uber is introducing a new flight service between n countries with n-1 flight routes connecting them. All flights are bi directional. The flight network forms a tree. Each country is either classified as Open or Restricted based on their current Covid 19 situation. Uber flights can freely visit any open country but are not allowed to land in or fly from restricted countries. However it can obtain special permission to convert some restricted to open countries. Due to a hardware malfunction, it can only convert the countries in pairs . Requesting more permissions than the number of restricted countries results in an error. For each country, determine the maximum number of countries that can be visited by Uber flights originating from that country, assuming optimal conversion of restricted to open. Each country obtains special permissions independently. Return the sum of the countries a flight can visit from each country.

Edit: u can make R to O in pairs... if no of R's in string are even, its a trivial case and answer is N*N (can open every city). If no of R's are odd, one city will have to be closed. While checking from different cities, this closed city may vary..

To clarify

Constraints

n <= 50005

Input Format

First line contains integer n denoting the number of country Second line contains a string of size n where s[i] denotes status of i'th country. R indicated country is restricted, O indicates country is Open. Third line has information about flight routes. Considering 1 based indexing, there is a flight from a[i] & i+1 in both directions

Sample Input 7 ROROROO 1 1 3 3 5 5

Output

Explanation:

Array of answer for each node : 4,4,5,5,5,5,5

My approach:

If no of restricted zones are even, answer is always n*n as we can open all.

If n is odd, I tried to maintain a DP state as dp[city] being the number of cities city could visit and I could find this in O(n) using DFS. However, the main problem is that this answer would be different if we have different starting points in the graph and would take O(n*2) which is too slow..