A tree is a graph with n vertices and exactly n - 1 edges; this graph should meet the following condition: there exists exactly one shortest (by number of edges) path between any pair of its vertices.

A subtree of a tree T is a tree with both vertices and edges as subsets of vertices and edges of T.

You're given a tree with n vertices. Consider its vertices numbered with integers from 1 to n. Additionally an integer is written on every vertex of this tree. Initially the integer written on the i-th vertex is equal to v_{i}. In one move you can apply the following operation:  Select the subtree of the given tree that includes the vertex with number 1.  Increase (or decrease) by one all the integers which are written on the vertices of that subtree. 

Calculate the minimum number of moves that is required to make all the integers written on the vertices of the given tree equal to zero.


-----Input-----

The first line of the input contains n (1 ≤ n ≤ 10^5). Each of the next n - 1 lines contains two integers a_{i} and b_{i} (1 ≤ a_{i}, b_{i} ≤ n; a_{i} ≠ b_{i}) indicating there's an edge between vertices a_{i} and b_{i}. It's guaranteed that the input graph is a tree. 

The last line of the input contains a list of n space-separated integers v_1, v_2, ..., v_{n} (|v_{i}| ≤ 10^9).


-----Output-----

Print the minimum number of operations needed to solve the task.

Please, do not write the %lld specifier to read or write 64-bit integers in С++. It is preferred to use the cin, cout streams or the %I64d specifier.


-----Examples-----
Input
3
1 2
1 3
1 -1 1

Output
3

Difficulty: MEDIUM_HARD
Tags: Tree algorithms

Dynamic programming

Graph traversal

Greedy algorithms
Skill types: Dynamic programming

Greedy algorithms

Starter code:

Solutions:
n = int(input())
r = [[] for i in range(n + 1)]
r[1] = [0]
for i in range(n - 1):
	(a, b) = map(int, input().split())
	r[a].append(b)
	r[b].append(a)
t = list(map(int, input().split()))
(u, v) = ([0] * (n + 1), [0] * (n + 1))
for (i, j) in enumerate(t, 1):
	if j < 0:
		u[i] = -j
	else:
		v[i] = j
(t, p) = ([1], [0] * (n + 1))
while t:
	a = t.pop()
	for b in r[a]:
		if p[b]:
			continue
		p[b] = a
		t.append(b)
k = [len(t) for t in r]
t = [a for a in range(2, n + 1) if k[a] == 1]
(x, y) = ([0] * (n + 1), [0] * (n + 1))
while t:
	a = t.pop()
	b = p[a]
	x[b] = max(x[b], u[a])
	y[b] = max(y[b], v[a])
	k[b] -= 1
	if k[b] == 1:
		t.append(b)
		if u[b] > 0:
			if x[b] - y[b] > u[b]:
				(u[b], v[b]) = (x[b], x[b] - u[b])
			else:
				(u[b], v[b]) = (y[b] + u[b], y[b])
		elif y[b] - x[b] > v[b]:
			(u[b], v[b]) = (y[b] - v[b], y[b])
		else:
			(u[b], v[b]) = (x[b], x[b] + v[b])
print(u[1] + v[1])


import os
import sys
from io import BytesIO, IOBase
from types import GeneratorType
from collections import defaultdict
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
sys.setrecursionlimit(2 * 10 ** 5)

def bootstrap(f, stack=[]):

	def wrappedfunc(*args, **kwargs):
		if stack:
			return f(*args, **kwargs)
		else:
			to = f(*args, **kwargs)
			while True:
				if type(to) is GeneratorType:
					stack.append(to)
					to = next(to)
				else:
					stack.pop()
					if not stack:
						break
					to = stack[-1].send(to)
			return to
	return wrappedfunc

@bootstrap
def dfs(u, p):
	s1 = 0
	s2 = 0
	for j in adj[u]:
		if j != p:
			r = (yield dfs(j, u))
			s1 = max(s1, r[0])
			s2 = max(s2, r[1])
	req = b[u - 1] - s1 + s2
	if req >= 0:
		yield [s1 + req, s2]
	else:
		yield [s1, s2 + abs(req)]
n = int(input())
adj = [[] for i in range(n + 1)]
for j in range(n - 1):
	(u, v) = map(int, input().split())
	adj[u].append(v)
	adj[v].append(u)
b = list(map(int, input().split()))
print(sum(dfs(1, 0)))


from collections import defaultdict
from sys import stdin, setrecursionlimit
setrecursionlimit(10 ** 6)
import threading

def dfs(g, node, parent, cr, req):
	l = [0, 0]
	for i in g[node]:
		if i != parent:
			t = dfs(g, i, node, cr, req)
			l[0] = max(t[0], l[0])
			l[1] = max(t[1], l[1])
	if l[0] - l[1] <= req[node]:
		l[0] += req[node] - (l[0] - l[1])
	else:
		l[1] += l[0] - l[1] - req[node]
	return l

def main():
	n = int(input())
	g = defaultdict(list)
	for i in range(n - 1):
		(a, b) = map(int, input().strip().split())
		g[a - 1].append(b - 1)
		g[b - 1].append(a - 1)
	req = list(map(int, input().strip().split()))
	cr = [0]
	x = dfs(g, 0, -1, cr, req)
	print(sum(x))
threading.stack_size(10 ** 8)
t = threading.Thread(target=main)
t.start()
t.join()


import os, sys
from io import BytesIO, IOBase

def main():
	n = int(input())
	path = [[] for _ in range(n)]
	for _ in range(n - 1):
		(u1, v1) = map(lambda xx: int(xx) - 1, input().split())
		path[u1].append(v1)
		path[v1].append(u1)
	val = list(map(int, input().split()))
	(st, poi, visi, dp) = ([0], [0] * n, [1] + [0] * (n - 1), [[0] * n for _ in range(2)])
	while len(st):
		(x, y) = (st[-1], path[st[-1]])
		if poi[x] != len(y) and visi[y[poi[x]]]:
			poi[x] += 1
		if poi[x] == len(y):
			st.pop()
			(a, b) = (dp[0][x], dp[1][x])
			ne = val[x] - a + b
			if len(st):
				if ne < 0:
					b -= ne
				else:
					a += ne
				dp[0][st[-1]] = max(dp[0][st[-1]], a)
				dp[1][st[-1]] = max(dp[1][st[-1]], b)
		else:
			st.append(y[poi[x]])
			visi[st[-1]] = 1
			poi[x] += 1
	print(abs(val[0] - dp[0][0] + dp[1][0]) + dp[0][0] + dp[1][0])
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
main()


from sys import stdin, stdout, setrecursionlimit
from collections import defaultdict, deque, Counter, OrderedDict
from heapq import heappop, heappush
import threading
n = int(stdin.readline())
graph = [set() for x in range(n)]
for x in range(n - 1):
	(a, b) = [int(x) for x in stdin.readline().split()]
	a -= 1
	b -= 1
	graph[a].add(b)
	graph[b].add(a)
vals = [int(x) for x in stdin.readline().split()]
bruh = [(0, -1)]
for x in range(n):
	(num, p) = bruh[x]
	for y in graph[num]:
		if y != p:
			bruh.append((y, num))
result = [-1 for x in range(n)]
for (v, parent) in bruh[::-1]:
	nP = 0
	nN = 0
	for x in graph[v]:
		if x != parent:
			(p, n) = result[x]
			nP = max(nP, p)
			nN = max(nN, n)
	nN = max(nN, nP + vals[v])
	nP = max(nP, nN - vals[v])
	result[v] = (nP, nN)
(ng, ps) = result[0]
vals[0] += ps - ng
stdout.write(str(ng + ps))


import sys

def minp():
	return sys.stdin.readline().strip()
n = int(minp())
e = [0]
p = [None] * (n + 1)
for i in range(n):
	e.append([])
for i in range(n - 1):
	(a, b) = map(int, minp().split())
	e[a].append(b)
	e[b].append(a)
v = list(map(int, minp().split()))
plus = [0] * (n + 1)
minus = [0] * (n + 1)
was = [False] * (n + 1)
was[1] = True
i = 0
j = 1
q = [0] * (n + 100)
q[0] = 1
p[1] = 0
while i < j:
	x = q[i]
	i += 1
	for y in e[x]:
		if not was[y]:
			was[y] = True
			p[y] = x
			q[j] = y
			j += 1
i = j - 1
while i >= 0:
	x = q[i]
	i -= 1
	s = minus[x] - plus[x]
	z = v[x - 1] + s
	pp = p[x]
	minus[pp] = max(minus[x], minus[pp])
	plus[pp] = max(plus[x], plus[pp])
	if z > 0:
		plus[pp] = max(plus[pp], plus[x] + z)
	elif z < 0:
		minus[pp] = max(minus[pp], minus[x] - z)
print(plus[0] + minus[0])