In a city, N water tanks are connected by pipeline(As a tree) where the ith tank has a capacity cap[i]. The ith element of the given Edge array of length N-1 represents that there is a pipeline between Edge[i][0] and Edge[i][1] tank. Since people working at the city corporation are lazy they usually select one of the tank and pour complete amount of water into it, when the tank is filled, the excess water evenly flows to the connected tanks. The head of city corporation has instructed to pour minimum amount of water into the selected tank so that all other tank is filled. As the labours of the corporation are not intelligent enough to figure out the minimum amount of water required to fill all the tanks they have asked your help. Also Maximum amount of water available with city corporation is 10^{18}.
NOTE: If the tank if full, the water flows to all of its connected tanks except the tank from which the water had come to it. i.e, to all tanks except the source for that particular tank. If it has no option to flow the water is considered to be wasted. S is the source tank.
Example 1:
Input:
N = 4 and S = 1
Edges = [[1, 2], [1, 3], [2, 4]]
Cap = [1, 1, 1, 1]
Output: 5
Explanation:
Initially 5 unit of water is poured into 
tank 1. 2 unit of it flows to tank 2 and 
2 unit of it flows into tank 3. From 2 
unit of water in tank 2, 1 unit flows into 
tank 4 and 1 unit from tank 3 is wasted.
 
Example 2:
Input:
N = 3 and S = 2
Edges = [[1, 2], [2, 3]]
Cap = [1, 1, 1]
Output: 3
Your Task:  
You don't need to read input or print anything. Your task is to complete the function minimum_amount() which takes an integer N, an integer S, 2-d array Edges, and an array Cap of length N as input parameters and returns the minimum amount of water required to fill all the tanks. If it is not possible to fill all the tanks print -1.
Expected Time Complexity: O(N*log(S))
Expected Auxiliary Space: O(1)
 
Constraints:
1 ≤ n ≤ 100000
1 ≤ s,u,v ≤ n
1 ≤ capacity of each tank ≤ 1000000007

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: Sorting

Graph algorithms

Data structures

Graph traversal

Starter code: #User function Template for python3





class Solution:

    def minimum_amount (self, Edges, num, start, Cap):

        # code here



Solutions:
import sys
sys.setrecursionlimit(10 ** 8)

class Solution:

	def minimum_amount(self, edges, N, S, cap):

		def recur(graph, visited, cur_node, cap):
			if visited[cur_node]:
				return -1
			visited[cur_node] = True
			cur_cap = cap[cur_node - 1]
			max_neigh_cap = 0
			neighbours = 0
			for neigh_node in graph[cur_node]:
				neigh_cap = recur(graph, visited, neigh_node, cap)
				if neigh_cap == -1:
					continue
				max_neigh_cap = max(max_neigh_cap, neigh_cap)
				neighbours += 1
			cur_cap += max_neigh_cap * neighbours
			return cur_cap
		graph = {i: [] for i in range(1, N + 1)}
		for (n1, n2) in edges:
			graph[n1].append(n2)
			graph[n2].append(n1)
		visited = [False] * (N + 1)
		res = recur(graph, visited, S, cap)
		for i in range(1, N + 1):
			if not visited[i]:
				return -1
		if res > 10 ** 18:
			return -1
		return res


from collections import deque

class Solution:

	def minimum_amount(self, Edges, num, start, Cap):
		adj = [[] for _ in range(num + 1)]
		for i in Edges:
			adj[i[0]].append(i[1])
			adj[i[1]].append(i[0])

		def bfs(S, adj, Cap, target):
			visited = [False] * (num + 1)
			visited[S] = True
			queue = deque()
			queue.append((S, target))
			while queue:
				(aux, remain) = queue.popleft()
				remain -= Cap[aux - 1]
				if remain < 0:
					return False
				n = len(adj[aux])
				if aux != S:
					n = n - 1
				if n == 0:
					continue
				left = remain // n
				for out in adj[aux]:
					if aux == out:
						continue
					if visited[out] == False:
						queue.append((out, left))
						visited[out] = True
			return True
		low = sum(Cap)
		high = 10 ** 18 + 1
		while low < high:
			mid = low + (high - low) // 2
			ans = bfs(start, adj, Cap, mid)
			if ans:
				high = mid
			else:
				low = mid + 1
		if low > 10 ** 18:
			return -1
		return low


import math
import sys
sys.setrecursionlimit(1000000000)

class GFG:
	rmx = int(1e+18)

	@staticmethod
	def dfs(node, num, cap, adj, vis, start):
		vis[node] = 1
		ans = cap[node - 1]
		mx = 0
		for child in adj[node]:
			if vis[child] != 1:
				cdfs = GFG.dfs(child, num, cap, adj, vis, start)
				if cdfs == -1:
					mx = -1
					break
				mx = max(mx, cdfs)
		if mx == -1:
			return -1
		if node == start:
			ans += len(adj[node]) * mx
		else:
			ans += (len(adj[node]) - 1) * mx
		if ans > GFG.rmx:
			return -1
		return ans

	@staticmethod
	def minimum_amount(Edges, num, start, cap):
		adj = [None] * (num + 1)
		i = 0
		while i < num + 1:
			adj[i] = []
			i += 1
		vis = [0] * (num + 1)
		i = 0
		while i < len(Edges):
			adj[Edges[i][0]].append(Edges[i][1])
			adj[Edges[i][1]].append(Edges[i][0])
			i += 1
		return GFG.dfs(start, num, cap, adj, vis, start)

class Solution:

	def minimum_amount(self, Edges, num, start, Cap):
		return GFG.minimum_amount(Edges, num, start, Cap)


from collections import defaultdict
import sys
sys.setrecursionlimit(10 ** 7)

class Solution:

	def minimum_amount(self, Edges, N, S, Cap):
		g = defaultdict(set)
		for (frm, to) in Edges:
			g[frm].add(to)
			g[to].add(frm)

		def dfs(node, amount, parent=None):
			nonlocal g, Cap
			amount -= Cap[node - 1]
			if amount < 0:
				return False
			n = len(g[node])
			if parent:
				n -= 1
			if n == 0:
				return True
			dist = amount // n
			for nxt in g[node]:
				if nxt == parent:
					continue
				if not dfs(nxt, dist, node):
					return False
			return True
		(lo, hi) = (sum(Cap), 10 ** 18 + 1)
		while lo < hi:
			mi = lo + (hi - lo) // 2
			if dfs(S, mi):
				hi = mi
			else:
				lo = mi + 1
		return -1 if lo > 10 ** 18 else lo


MAX = int(1e+18)
from collections import deque

def solve(adj, u, A, mid):
	N = len(A)
	q = deque()
	q.append([u, mid])
	vis = [0 for i in range(N + 1)]
	while q:
		(nd, water) = q.popleft()
		vis[nd] = 1
		c = 0
		if A[nd - 1] > water:
			return 0
		water -= A[nd - 1]
		for i in adj[nd]:
			if vis[i] == 0:
				c += 1
		if c > 0:
			water //= c
		for i in adj[nd]:
			if vis[i] == 0:
				q.append([i, water])
	return 1

class Solution:

	def minimum_amount(self, Edges, N, start, Cap):
		adj = [[] for i in range(N + 1)]
		for (u, v) in Edges:
			adj[u].append(v)
			adj[v].append(u)
		l = 0
		r = MAX
		ans = -1
		while l <= r:
			mid = l + r >> 1
			if solve(adj, start, Cap, mid):
				ans = mid
				r = mid - 1
			else:
				l = mid + 1
		return ans


from collections import deque

class Solution:

	def minimum_amount(self, Edges, num, start, cap):

		def check(gr, num, start, cap, water):
			vis = [0] * 100010
			q = deque()
			q.append([start, water])
			while q:
				val = q.popleft()
				curr = val[0]
				curr_water = val[1]
				vis[curr] = 1
				if cap[curr - 1] > curr_water:
					return 0
				curr_water -= cap[curr - 1]
				neighbour = 0
				for it in gr[curr]:
					nxt = it
					if vis[nxt] == 0:
						neighbour += 1
				if neighbour > 0:
					curr_water = curr_water // neighbour
				for it in gr[curr]:
					nxt = it
					if vis[nxt] == 0:
						q.append([nxt, curr_water])
			return 1
		hi = 10 ** 18 + 1
		lo = 0
		maxx = 10 ** 18 + 1
		gr = [[] for i in range(100011)]
		for i in range(num - 1):
			gr[Edges[i][0]].append(Edges[i][1])
			gr[Edges[i][1]].append(Edges[i][0])
		while hi >= lo:
			mid = (hi + lo) // 2
			if mid >= maxx:
				return -1
			if check(gr, num, start, cap, mid) == 0:
				lo = mid + 1
			else:
				hi = mid - 1
		return lo


from sys import setrecursionlimit as srt
srt(10 ** 6)

class Solution:

	def minimum_amount(self, Edges, n, start, cap):
		possible = True

		def f(i, c, p=-1):
			nonlocal possible
			if possible == False:
				return
			z = len(x[i]) - (0 if p == -1 else 1)
			if c < cap[i]:
				possible = False
				return
			if z == 0:
				return
			z = (c - cap[i]) / z
			for j in x[i]:
				if j != p:
					f(j, z, i)
		x = [[] for i in range(n)]
		for (a, b) in Edges:
			x[a - 1].append(b - 1)
			x[b - 1].append(a - 1)
		i = sum(cap)
		j = 10 ** 18
		ans = -1
		while i <= j:
			possible = True
			m = (i + j) // 2
			f(start - 1, m)
			if possible:
				ans = m
				j = m - 1
			else:
				i = m + 1
		return ans