The government has invited bids from contractors to run canteens at all railway stations. Contractors will be allowed to bid for the catering contract at more than one station. However, to avoid monopolistic price-fixing, the government has declared that no contractor may bid for a pair of neighbouring stations.
The railway network has exactly one route between any pair of stations. Each station is directly connected by a railway line to at most $50$ neighbouring stations.
To help contractors plan their bids, the government has provided data on the number of passengers who pass through each station each year. Contractors would like to bid for stations with a higher volume of passenger traffic to increase their turnover.
For instance, suppose the railway network is as follows, where the volume of passenger traffic is indicated by the side of each station.

In this network, the best option for the contractor is to bid for stations $1, 2, 5$ and $6$, for a total passenger volume of $90$.
Your task is to choose a set of stations that the contractor should bid for so that the total volume of traffic across all the stations in the bid is maximized.

-----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, ..., 2N$, 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 total volume of traffic across the set of stations in the optimal bid made by the contractor.

-----Constraints:-----
- $1 \leq N \leq 100000$. 
- Each railway station has at most $50$ neighbours.

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

-----Sample Output-----
90

```python

USER_FILENAME = "<user_code>"
import sys, json, builtins
import math, heapq, bisect, itertools, functools, collections, statistics, fractions, decimal, operator, array, random, re, string, os, pathlib
try:
    import resource as _res
except Exception:
    _res = None
from collections import Counter, defaultdict, deque, OrderedDict
from functools import lru_cache, reduce
from itertools import accumulate, permutations, combinations, product
from math import gcd, ceil, floor, sqrt
from decimal import Decimal
try:
    from typing import *
except Exception:
    pass
try:
    sys.setrecursionlimit(1_000_000)
except Exception:
    pass
try:
    import site as _site
    try:
        _sys_sites = _site.getsitepackages() if hasattr(_site, "getsitepackages") else []
        for _p in _sys_sites:
            if _p and _p not in sys.path:
                sys.path.append(_p)
    except Exception:
        pass
    try:
        _usp = _site.getusersitepackages()
        if isinstance(_usp, str):
            _usp = [_usp]
        for _p in _usp:
            if _p and _p not in sys.path:
                sys.path.append(_p)
    except Exception:
        pass
except Exception:
    pass

ns = {"__name__": "__main__"}
for _k, _v in list(globals().items()):
    if not _k.startswith("_"):
        ns[_k] = _v
_CODE = 'n=int(input())\r\nl=[]\r\ndp=[]\r\nd={}\r\nfor i in range(n):\r\n\tl.append(int(input()))\r\n\td[i]=[]\r\n\tdp.append([0,0])\r\n\r\nfor i in range(n-1):\r\n\ta,b=list(map(int,input().split()))\r\n\td[a-1].append(b-1)\r\n\td[b-1].append(a-1)\r\n#print(l)\r\n#print(d)\r\n\r\ndef dfs(ch,pa,visited):\r\n\tdp[ch][1]=l[ch]\r\n\t#print(dp[ch],ch+1)\r\n\tfor i in range(len(d[ch])):\r\n\t\tif d[ch][i] not in visited:\r\n\t\t\tvisited.add(d[ch][i])\r\n\t\t\tdfs(d[ch][i],ch,visited)\r\n\t\t\tdp[ch][0]+=max(dp[d[ch][i]][0],dp[d[ch][i]][1])\r\n\t\t\tdp[ch][1]+=dp[d[ch][i]][0]\r\n\t\t\t#print(ch+1,dp[ch])\r\nv=set()\r\nv.add(0)\r\ndfs(0,-1,v)\r\n\r\n#print(dp)\r\nprint(max(dp[0][0],dp[0][1]))\r\n\r\n\t\r\n\r\n\r\n'
_co = compile(_CODE, USER_FILENAME, "exec")
exec(_co, ns, ns)

```

Measured memory_bytes: 13399