A key feature of the Siruseri railway network is that it has exactly one route between any pair of stations.
The government has chosen three contractors to run the canteens at the stations on the railway network. To ensure that there are no disputes between the contractors it has been decided that if two stations, say $A$ and $B$, are assigned to a particular contractor then all the stations that lie on the route from $A$ to $B$ will also be awarded to the same contractor.
The government would like the assignment of stations to the contractors to be as equitable as possible. The government has data on the number of passengers who pass through each station each year. They would like to assign stations so that the maximum number of passengers passing through any contractor's collection of stations is minimized.
For instance, suppose the railway network is as follows, where the volume of passenger traffic is indicated by the side of each station.

One possible assignment would to award stations $1$ and $3$ to one contractor (there by giving him a traffic of $35$ passengers), station $2$ to the second contractor (traffic of $20$) and stations $4, 5$ and $6$ to the third contractor (traffic of $100$). In this assignment, the maximum traffic for any one contractor is 100. On the other hand if we assigned stations $1, 2$ and $3$ to one contractor, station $4$ and $6$ to the second contractor and station $5$ to the third contractor the maximum traffic for any one contractor is $70$. You can check that you cannot do better. (The assignment $1$, $2$ and $3$ to one contractor, $4$ to the second contractor, and $5$ and $6$ to the third contractor has a lower value for the maximum traffic ($55$) but it is not a valid assignment as the route from $5$ to $6$ passes through $4$.)

-----Input:-----
The first line of the input contains one integer $N$ indicating the number of railways stations in the network. The stations are numbered $1,2,..., N$. This is followed by $N$ lines of input, lines $2,3,...,N+1$, indicating the volume of traffic at each station. The volume of traffic at station $i$, $1 \leq i \leq N$, is given by a single integer in line $i+1$. The next $N-1$ lines of input, lines $N+2, N+3, ..., 2 \cdot N$, describe the railway network. Each of these lines contains two integers, denoting a pair of stations that are neighbours.

-----Output:-----
The output should be a single integer, corresponding to the minimum possible value of the maximum traffic of any contractor among all valid assignment of the stations to the three contractors.

-----Constraints:-----
- $1 \leq N \leq 3000$.

-----Sample Input-----
6
10
20
25
40
30
30
4 5
1 3
3 4
2 3
6 4

-----Sample Output-----
70

Difficulty: interview

Starter code:

Solutions:
n=int(input())
cost=[]
d={}
val_desc=[0]*n
visited=set()
visited.add(0)
dfstack=[]
desc = [[False for i in range(n)] for i in range(n)]
for i in range(n):
	cost.append(int(input()))
	d[i]=[]

for i in range(n-1):
	j,k=list(map(int,input().split()))
	d[j-1].append(k-1)
	d[k-1].append(j-1)

def dfs(u):
	val_desc[u]+=cost[u]
	dfstack.append(u)
	for i in dfstack:
		desc[u][i]=True
	for i in d[u]:
		if i not in visited:
			visited.add(i)
			dfs(i)
			val_desc[u]+=val_desc[i]			
	dfstack.pop(-1)

dfs(0)
mp=10**9
coco=sum(cost)
for i in range(n):
	for j in range(i+1,n):
		vali=val_desc[i]
		valj=val_desc[j]
		if desc[i][j]:
			valj-=val_desc[i]
		if desc[j][i]:
			vali-=val_desc[j]
		p=max(vali,valj,coco-vali-valj)
		mp=min(mp,p)
#print(desc)
#print(val_desc)
#print
print(mp)


	


#for _ in range(int(input()):
#n,m = map(int,input().split())
#x = [int(w) for w in input().split()]
#n = int(input())
#x = [int(input()) for _ in range(n)]
#for i in range(n):
#dt = {} for i in x:dt[i] = dt.get(i,0)+1
#dt = {k:v for k,v in sorted(x.items(), key=lambda i: i[1])}

def dfs(v):
    visited.add(v)
    parents.append(v)
    for u in parents:
        desc[v][u] = True
    for u in graph[v]:
        if u not in visited:
            dfs(u)
            val[v] += val[u]
    parents.pop()


n = int(input())
cost,graph,val = {},{},{}
# val(i) is sum of cost of descendants of i
for i in range(1,n+1):
    cost[i] = int(input())
    graph[i] = []
    val[i] = cost[i]
for _ in range(n-1):
    a,b = map(int,input().split())
    graph[a].append(b)
    graph[b].append(a)

desc = [[False for i in range(n+1)] for i in range(n+1)]
# desc(i,j) is true if i is descendant of j
visited = set()
parents =[]   # Ancestors stack


dfs(1)
total = sum(cost.values())
best = float('inf')
for i in range(1,n):
    for j in range(i+1,n+1):
        split = 0
        s1 = val[i]
        s2 = val[j]
        if desc[i][j]:
            s2 -= val[i]
        if desc[j][i]:
            s1 -= val[j]
        s3 = total-s1-s2
        split = max(s1,s2,s3)
        best = min(best,split)
print(best)