### PROBLEM LINK:

**Author:** Roman Furko

**Tester:** Sergey Kulik

**Editorialist:** Mugurel Ionut Andreica

### DIFFICULTY:

HARD

### PREREQUISITES:

Graphs,Treaps,Segment trees

### PROBLEM:

Two players are playing a game on an undirected graph with weights on its edges. The players move in turns. At his turn, a player chooses an unmarked vertex and marks it with the player’s color. The game ends when all the nodes have been marked. At the end of the game the score of each player is equal to the sum of the weights of those edges having both endpoints marked in the player’s color. Let’s denote by **Score(i)** the score of player **i**. During the game each of the two players tries to maximize the difference between their score and the score of the opponent (i.e. player **i** tries to maximize **Score(i)-Score(3-i)**).

You need to decide what is the maximum difference between the score of player 1 (i.e. the player making the first move) and that of player 2, assuming that both players play optimally.

In addition, the edges are added to the graph one by one and you need to find the maximum difference for each game played from scratch on the graph obtained after adding every edge.

### QUICK EXPLANATION:

Let’s define a weight for each node: **w(i)**=the sum of weights of all the edges incident with the node **i**. At their turn, the optimal move for each player is to mark the unmarked vertex **i** with the maximum value **w(i)**.

Let’s consider these node weights sorted in descending order: **w(p(1)) >= w(p(2)) >= … >= w(p(N))**. Player 1 will mark all the nodes **p(i)** with odd **i**, while player 2 will mark all the vertices **p(j)** with even **j**.

Let’s compute the value DIF=\sum_{i=1}^{2*i-1≤N}{w(p(2*i-1))}-\sum_{i=1}^{2*i≤N}{w(p(2*i))}. **DIF** is equal to twice the maximum difference between the scores of player 1 and player 2. Why? It’s easy to see that if an edge **(i,j)** has both endpoints marked with the same color, then its weight will be considered both in **wp(i)** and in **wp(j)**. However, if its endpoints have different colors, its weight will appear once with the sign **+** (for player 1) and once with the sign **-**, effectively contributing **zero** to **DIF**.

After the addition of every edge we need to update the weights of the nodes incident to it and then update **DIF**. In order to do this efficiently we need to use data structures which support logarithmic updates (e.g. treaps, segment trees).

### EXPLANATION:

Let’s see why the optimal strategy in a game is to always pick the unmarked vertex with the largest weight. As we saw, the difference between the score of the first player and that of the second player is twice the difference between the weights of the vertices selected by the first player and those selected by the second player. Thus, in order to maximize his score, a player will want to select vertices with larger weights. Moreover, if a player **A** doesn’t select the unmarked vertex with the largest weight, then the other player (**B**) will be able to select it and, thus, player **A** will obtain a lower score, while player **B** will obtain a higher score. This is sufficient motivation for player **A** to pick the unmarked vertex with the largest weight.

We now have a way of solving the problem, but not in a very efficient way. After adding a new edge we update the weights of the endpoints of the edge, sort the vertices again (either in **O(Nxlog(N))** time, or in **O(N)** time, since we just need to change the position of at most two vertices) and then recompute **DIF**. This has a time complexity of **O(MxNxlog(N))** (or **O(MxN)**) and is too slow for obtaining 100 points.

In order to obtain 100 points we need to recompute **DIF** more efficiently. I will present here an approach based on using a segment tree.

We will create **O(N+M)** tuples **(i,k,weight)**, one for each time a vertex’s weight **w(i)** is updated after adding a new edge. We will initially have **N** vertex tuples corresponding to the **N** initial vertices, all of them having weight zero. We also initialize all the values **w(i)** to **0**. Then we start adding the edges one by one. Let’s assume that the current edge has index **k**, has cost **c** and connects the vertices **i** and **j**. If i
eq j then we increment both **w(i)** and **w(j)** by **c** and then we add two new tuples **(i,k,w(i))** and **(j,k,w(j))**. If i=j then we increment **w(i)** by **2xc** and we only add one tuple **(i,k,w(i))**.

Once we have all these tuples we sort them in decreasing order of the parameter **weight**. For each edge with index **k** we will maintain the positions of the two (or one) tuples added for this edge in the sorted order. Let these positions be **pa(k)** and **pb(k)**.

We will now construct a segment tree over the **O(N+M)** tuples, but only the **N** initial tuples will be *enabled*. Each node of the segment tree will contain two values: **maxdif**=the maximum difference that player 1 can obtain if he plays considering only the tuples enabled in this node’s interval, and **cnt**=how many tuples are enabled in this node’s interval. The answer we are interested in will always be available at the root of the segment tree.

We will now add edges one by one. At the same time we will maintain for each vertex **i** a value **pos(i)**=the position of the only enabled tuple corresponding to vertex **i** (this is because at each moment we will have **exactly one** tuple enabled for each vertex, i.e. **N** tuples enabled overall). Let’s assume that the current edge is **k** and connects the vertices **i** and **j**. Let’s consider the case i
eq j first. We need to *disable* the tuples on the positions **pos(i)** and **pos(j)** and then enable the tuples on the positions **pa(k)** and **pb(k)**. Afterwards we set **pos(i)=pa(k)** and **pos(j)=pb(k)**.

The case i=j is similar. We disable the tuple on the position **pos(i)**, enable the tuple on the position **pa(k)** and then set **pos(i)=pa(k)**.

Note that we perform **O(N+M)** *Enable* and *Disable* operations. In the pseudocode below you can see how to perform each of these operations in **O(log(N+M))** time using the segment tree.

void UpdateSegmentTree(int node, int op) { // node = segment tree leaf node corresponding to the updated tuple // op = 1, for enabling the tuple; -1, for disabling the tuple if (op < 0) segtree[node].maxdif = segtree[p].cnt = 0; else { // tuple(node) is the tuple corresponding to the segment tree leaf node *node* segtree[node].maxdif = tuple(node).weight; segtree[node].cnt = 1; } node >>= 1; while (node >= 1) { int left_child = (node <>= 1; } }

The overall time complexity is **(O(N+M)xlog(N+M))**.

### AUTHOR’S, TESTER’S AND EDITORIALIST’S SOLUTIONS:

Author’s solution can be found here.

Tester’s solution can be found here.

Editorialist’s solution can be found here.