Question 1) (Based on Graphs) 1)We are given an undirected graph with no edge weights and each node is numbered from 1 to n .Each node contains a value which will be given as a separate array with 1-based indexing. There are two players and they play with this graph using following rules: 1)Player1 selects one node and removes that node including the edges connected to it in order to break it into two or more parts. 2)Now ,Player2 now selects the connected component of the graph such that the sum of all values in the nodes of selected component is maximum. 3)Now, Player1 selects the connected component from the remaining connected components . Scores of each player is the sum of values at all nodes of the connected component of graph which was selected by them and each player wants to maximize his/her score .Assume each player optimally. we need to output the scores of player1 and player2.
Question 2) (Based on Trees) In this question we are given a binary tree in which some nodes are colored in white and some nodes in black color.We can color the given tree by following the below rules: 1)We can color only white nodes means only the white nodes from the given tree can be converted in to black nodes. Reverse in not possible. 2)We can color any white node in to black node if and only if the parent of white node is a black node. Using above mentioned rules we have to find the number of different possible trees which can be obtained by coloring the given tree using the above rules.
If there are any similar problems of this type please share them with me. Thank You :)