Alice and Bob are playing a game. They are given a connected undirected graph containing n nodes and medges. Each node has
sweetness value denoted by an array w.
Alice moves first,
1. In the first move. Alice may break a node. Each edge connected to this node will vanish.
2. In the second move, Bob will pick any connected component containing some (or all) nodes. 3. In the third move, Alice will pick any remaining connected components if there are any.
The game then ends in three steps. Both of them want to maximize their score by collecting the maximum possible sweetnes are not trying to minimize each other's scores.
Task
Determine the maximum score of Alice and Bob respectively. Assume both play the game optimally
Notes
• 1-based indexing is followed.
• A connected component is the maximal set of nodes in which any two nodes of that component are connected to
or more paths.
Max score: 100
2021/06/13 11:07
• The sweetness value of a connected component is the sum of the sweetness value of all the nodes in that comm
there are no connected components, assume the sum equals 0.
Answers
Answer:
It's a articulation graphs problem
use a DFS TREE to solve the problem.
Explanation:
1. The sweetness value of u will be denoted as sw[u] in the following. Create the graph's DFS tree. Store the total sweetness value of the subtree of each vertex v in a variable called sub[v].
2. Consider deleting some of the vertices u. What related components remain after the vertex u has been removed? There will be a component with total sweetness value sub[v] for every child v of u such that there is no back-edge from a descendant of v to a suitable ancestor of u.
3. The remaining vertices will be in a single connected component linked to u's parent. We know the sizes of all these components, so we can calculate the value of the largest, give it to Bob, and give the rest to Alice. If Alice removes the vertex u first, we may verify the scores of both players. Calculate these results for each u option.