Need help in developing the python code The kingdom of Ererraveth has N cities and N−1 roads. A single road connects 2 cities. From any city it is possible to reach all other cities via the roads. It can be deduced that there is a unique path between any 2 cities. Each city is labeled with a unique number 1 to N. The city where the royal palace is located is assigned number 1.
Need help in developing the python code
The kingdom of Ererraveth has N cities and N−1 roads. A single road connects 2 cities. From any city it is possible to reach all other cities via the roads. It can be deduced that there is a unique path between any 2 cities. Each city is labeled with a unique number 1 to N. The city where the royal palace is located is assigned number 1.
The evil prince Drach who was once banished is planning to return and claim the empire for himself. First, he will capture the royal palace. Next, he will have his revenge on the lords of the cities. To punish a city, he will simply destroy all roads that connect it to its neighbouring cities, and the city will slowly starve.
However, there are KK cities whose lords have supported Drach in the past. Let's call these good cities. Drach will ensure that all good cities remain connected via roads to his royal palace. Thus any city which is not good but lies on the path from the royal palace to a good city will be spared. But if the lord of any good city is removed from his post by the time Drach is back, he will no longer consider it a good city.
Let G be the set of potentially good cities with |G|=K, and G′ be a subset of G. Drach wants to know the number of roads he will have to destroy if G′ be the set of good cities, i.e. if all cities in G′ remain connected to his palace in city 1 and all cities that are not essential for the above are punished. You will need to calculate the bitwise XOR-sum of the results for all the 2K possible subsets G′.
Input:
7
1 2
1 3
1 4
2 5
3 6
3 7
2
2 7
Output:
4
Trending now
This is a popular solution!
Step by step
Solved in 2 steps with 1 images
