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 vi. In one move you can apply the following operation:

  1. Select the subtree of the given tree that includes the vertex with number 1. 
  2. 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 ≤ 105). Each of the next n - 1 lines contains two integers ai and bi (1 ≤ ai, bi ≤ n; ai ≠ bi) indicating there's an edge between vertices ai and bi. It's guaranteed that the input graph is a tree. 

The last line of the input contains a list of n space-separated integers v1, v2, ..., vn (|vi| ≤ 109).

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
import java.io.IOException;
import java.io.OutputStreamWriter;
import java.io.BufferedWriter;
import java.util.InputMismatchException;
import java.util.ArrayList;
import java.io.OutputStream;
import java.io.PrintWriter;
import java.io.Writer;
import java.io.InputStream;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 * @author Diego Huerfano ( diego.link )
 */
public class Main {
	public static void main(String[] args) {
		InputStream inputStream = System.in;
		OutputStream outputStream = System.out;
		InputReader in = new InputReader(inputStream);
		OutputWriter out = new OutputWriter(outputStream);
		TaskD solver = new TaskD();
		solver.solve(1, in, out);
		out.close();
	}
}

class TaskD {

    private long value[];
    private int n;
    private ArrayList< ArrayList<Integer> > t=new ArrayList<ArrayList<Integer>>();
    private boolean vst[]=new boolean[ (int)1e5+100];

    private Pair<Long, Long> getCost( int u ) {
        long pos=0;
        long neg=0;
        vst[u]=true;
        for( int v : t.get(u) ) {
            if( vst[v] ) continue;
            Pair<Long, Long> p = getCost( v );
            pos=Math.max(p.first, pos);
            neg=Math.max(p.second, neg);
        }
        long newValue=value[u]+pos-neg;
        if( newValue>0 ) neg+=newValue;
        if( newValue<0 ) pos+=Math.abs( newValue );
        return new Pair<Long, Long>( pos, neg );
    }

    public void solve(int testNumber, InputReader in, OutputWriter out) {
        n=in.readInt();
        for( int i=0; i<n; i++ )
            t.add( new ArrayList<Integer>() );
        for( int i=0; i<n-1; i++ ) {
            int a=in.readInt()-1;
            int b=in.readInt()-1;
            t.get( a ).add( b );
            t.get( b ).add( a );
        }
        value=in.readLongs( n );
        Pair<Long, Long> ans=getCost( 0 );
        out.printLine( ans.first + ans.second );
    }
}

class Pair<U extends Comparable<U>, V extends Comparable<V> > implements Comparable<Pair<U, V> >{

    public U first;
    public V second;

    public Pair( U first, V second ) {
        this.first =first;
        this.second=second;
    }

    public boolean equals(Object o) {
        if (this == o) return true;
        if (!(o instanceof Pair)) return false;
        Pair pair = (Pair) o;
        if (!first.equals(pair.first)) return false;
        if (!second.equals(pair.second)) return false;
        return true;
    }

    public int hashCode() {
        int result = first.hashCode();
        result = 31 * result + second.hashCode();
        return result;
    }

    public int compareTo(Pair<U, V> o) {
        int cmp=first.compareTo( o.first );
        if( cmp==0 ) return second.compareTo( second );
        else return cmp;
    }
}

class InputReader {

    private InputStream stream;
    private byte[] buf = new byte[1024];
    private int curChar;
    private int numChars;
    private SpaceCharFilter filter;

    public InputReader(InputStream stream) {
        this.stream = stream;
    }

    public int read() {
        if (numChars == -1)
            throw new InputMismatchException();
        if (curChar >= numChars) {
            curChar = 0;
            try {
                numChars = stream.read(buf);
            } catch (IOException e) {
                throw new InputMismatchException();
            }
            if (numChars <= 0)
                return -1;
        }
        return buf[curChar++];
    }

    public int readInt() {
        int c = read();
        while (isSpaceChar(c))
            c = read();
        int sgn = 1;
        if (c == '-') {
            sgn = -1;
            c = read();
        }
        int res = 0;
        do {
            if (c < '0' || c > '9')
                throw new InputMismatchException();
            res *= 10;
            res += c - '0';
            c = read();
        } while (!isSpaceChar(c));
        return res * sgn;
    }

    public long readLong() {
        int c = read();
        while (isSpaceChar(c))
            c = read();
        int sgn = 1;
        if (c == '-') {
            sgn = -1;
            c = read();
        }
        long res = 0;
        do {
            if (c < '0' || c > '9')
                throw new InputMismatchException();
            res *= 10;
            res += c - '0';
            c = read();
        } while (!isSpaceChar(c));
        return res * sgn;
    }

    public long[] readLongs( int n ){
        long ans[]=new long[n];
        for( int i=0; i<n; i++ ) ans[i]=readLong();
        return ans;
    }

    public boolean isSpaceChar(int c) {
        if (filter != null)
            return filter.isSpaceChar(c);
        return isWhitespace(c);
    }

    public static boolean isWhitespace(int c) {
        return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
    }

    public interface SpaceCharFilter {
        public boolean isSpaceChar(int ch);
    }
}

class OutputWriter {
    private final PrintWriter writer;

    public OutputWriter(OutputStream outputStream) {
        writer = new PrintWriter(new BufferedWriter(new OutputStreamWriter(outputStream)));
    }

    public OutputWriter(Writer writer) {
        this.writer = new PrintWriter(writer);
    }

    public void print(Object...objects) {
        for (int i = 0; i < objects.length; i++) {
            if (i != 0)
                writer.print(' ');
            writer.print(objects[i]);
        }
    }

    public void printLine(Object...objects) {
        print( objects );
        writer.println();
    }

    public void close() {
        writer.close();
    }
}

