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
33
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..
