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..
I am not getting the problem completely like is their any restriction on the conversion count (making R->O) and explanation regarding the example testcase.
Hey sorry, for not being clear.. 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.. hope u get it now
Auto comment: topic has been updated by sirius2211 (previous revision, new revision, compare).
Maybe we can use Dp to store the subtree size from each node, by this way, all the connected nodes which are odd number of restricted, we will subtract the minimal subtree node size from it, and do that for all odd connected restricted, and when the node itself is the minimal subtree node, then we can subtract the second minimal subtree size from it for that odd connected component, and rest remain same.
But in that case lets say for node no.5: if we convert itself and maximum subtree (i.e rooted at 1) we should get the max. ans but in this case we are keeping 3 as our restricted node and hence we will not even be able to reach 1.