AtCoder Regular Contest 098 - Donation

There is a simple undirected graph with N vertices and M edges.
The vertices are numbered 1 through N, and the edges are numbered 1 through M.
Edge i connects Vertex U_i and V_i.
Also, Vertex i has two predetermined integers A_i and B_i.
You will play the following game on this graph.
First, choose one vertex and stand on it, with W yen (the currency of Japan) in your pocket.
Here, A_s \leq W must hold, where s is the vertex you choose.
Then, perform the following two kinds of operations any number of times in any order:
 - Choose one vertex v that is directly connected by an edge to the vertex you are standing on, and move to vertex v. Here, you need to have at least A_v yen in your pocket when you perform this move.
 - Donate B_v yen to the vertex v you are standing on. Here, the amount of money in your pocket must not become less than 0 yen.
You win the game when you donate once to every vertex.
Find the smallest initial amount of money W that enables you to win the game.

-----Constraints-----
 - 1 \leq N \leq 10^5
 - N-1 \leq M \leq 10^5
 - 1 \leq A_i,B_i \leq 10^9
 - 1 \leq U_i < V_i \leq N
 - The given graph is connected and simple (there is at most one edge between any pair of vertices).

-----Input-----
Input is given from Standard Input in the following format:
N M
A_1 B_1
A_2 B_2
:
A_N B_N
U_1 V_1
U_2 V_2
:
U_M V_M

-----Output-----
Print the smallest initial amount of money W that enables you to win the game.

-----Sample Input-----
4 5
3 1
1 2
4 1
6 2
1 2
2 3
2 4
1 4
3 4

-----Sample Output-----
6

If you have 6 yen initially, you can win the game as follows:
 - Stand on Vertex 4. This is possible since you have not less than 6 yen.
 - Donate 2 yen to Vertex 4. Now you have 4 yen.
 - Move to Vertex 3. This is possible since you have not less than 4 yen.
 - Donate 1 yen to Vertex 3. Now you have 3 yen.
 - Move to Vertex 2. This is possible since you have not less than 1 yen.
 - Move to Vertex 1. This is possible since you have not less than 3 yen.
 - Donate 1 yen to Vertex 1. Now you have 2 yen.
 - Move to Vertex 2. This is possible since you have not less than 1 yen.
 - Donate 2 yen to Vertex 2. Now you have 0 yen.
If you have less than 6 yen initially, you cannot win the game. Thus, the answer is 6.

Difficulty: VERY_HARD

Starter code:

Solutions:
class dsu:

	def __init__(self, n=0):
		self._n = n
		self.parent_or_size = [-1] * n

	def merge(self, a: int, b: int) -> int:
		x = self.leader(a)
		y = self.leader(b)
		if x == y:
			return x
		if self.parent_or_size[x] > self.parent_or_size[y]:
			(x, y) = (y, x)
		self.parent_or_size[x] += self.parent_or_size[y]
		self.parent_or_size[y] = x
		return x

	def same(self, a: int, b: int) -> bool:
		return self.leader(a) == self.leader(b)

	def leader(self, a: int) -> int:
		x = a
		while self.parent_or_size[x] >= 0:
			x = self.parent_or_size[x]
		while a != x:
			(self.parent_or_size[a], a) = (x, self.parent_or_size[a])
		return x

	def size(self, a: int) -> int:
		return -self.parent_or_size[self.leader(a)]

	def groups(self):
		g = [[] for _ in range(self._n)]
		for i in range(self._n):
			g[self.leader(i)].append(i)
		return list((c for c in g if c))
(n, m) = list(map(int, input().split()))
vdata = []
for _ in range(n):
	(a, b) = list(map(int, input().split()))
	vdata.append((max(a - b, 0), b))
to = [[] for _ in range(n)]
for _ in range(m):
	(u, v) = list(map(int, input().split()))
	u -= 1
	v -= 1
	to[u].append(v)
	to[v].append(u)
s = dsu(n)
dp = vdata.copy()
visited = [False] * n
for u in sorted(list(range(n)), key=lambda i: vdata[i][0]):
	(req, gain) = vdata[u]
	frm = {u}
	for v in to[u]:
		if visited[v]:
			frm.add(s.leader(v))
	mnextra = 10 ** 18
	for v in frm:
		(e, g) = dp[v]
		e += max(req - (e + g), 0)
		if e < mnextra:
			(mnextra, mni) = (e, v)
	(extra, tot_gain) = (mnextra, sum((dp[v][1] for v in frm)))
	for v in frm:
		s.merge(u, v)
	dp[s.leader(u)] = (extra, tot_gain)
	visited[u] = True
ans = sum(dp[s.leader(0)])
print(ans)


import os
import sys
if os.getenv('LOCAL'):
	sys.stdin = open('_in.txt', 'r')
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
IINF = 10 ** 18
MOD = 10 ** 9 + 7

class UnionFind:

	def __init__(self, size=None, nodes=None):
		assert size is not None or nodes is not None
		if size is not None:
			self._parents = [i for i in range(size)]
			self._ranks = [0 for _ in range(size)]
			self._sizes = [1 for _ in range(size)]
		else:
			self._parents = {k: k for k in nodes}
			self._ranks = {k: 0 for k in nodes}
			self._sizes = {k: 1 for k in nodes}

	def unite(self, x, y):
		x = self.root(x)
		y = self.root(y)
		if x == y:
			return
		if self._ranks[x] > self._ranks[y]:
			self._parents[y] = x
			self._sizes[x] += self._sizes[y]
		else:
			self._parents[x] = y
			self._sizes[y] += self._sizes[x]
			if self._ranks[x] == self._ranks[y]:
				self._ranks[y] += 1

	def root(self, x):
		if self._parents[x] == x:
			return x
		self._parents[x] = self.root(self._parents[x])
		return self._parents[x]

	def size(self, x):
		return self._sizes[self.root(x)]

def argsort(li, key=None, reverse=False):
	return [i for (_, i) in sorted([(a, i) for (i, a) in enumerate(li)], key=(lambda t: key(t[0])) if key else None, reverse=reverse)]
(N, M) = list(map(int, sys.stdin.buffer.readline().split()))
(A, B) = list(zip(*[map(int, sys.stdin.buffer.readline().split()) for _ in range(N)]))
VU = [list(map(int, sys.stdin.buffer.readline().split())) for _ in range(M)]
graph = [[] for _ in range(N)]
for (v, u) in VU:
	v -= 1
	u -= 1
	graph[v].append(u)
	graph[u].append(v)
reqs = [max(a, b) for (a, b) in zip(A, B)]
uses = list(B)
idx = argsort([a - b for (a, b) in zip(A, B)])
uf = UnionFind(size=N)
seen = [False] * N
ans = [INF] * N
for v in idx:
	seen[v] = True
	roots = set()
	for u in graph[v]:
		if not seen[u]:
			continue
		roots.add(uf.root(u))
	use_all = uses[v]
	for r in roots:
		use_all += uses[r]
	req_v = reqs[v] + use_all - uses[v]
	for r in roots:
		req_v = min(req_v, max(reqs[r], reqs[v] - uses[v]) + use_all - uses[r])
	for r in roots:
		uf.unite(v, r)
	reqs[uf.root(v)] = req_v
	uses[uf.root(v)] = use_all
ans = reqs[uf.root(0)]
print(ans)