男神的树-j9国际

1164: 男神的树

时间限制: 2000 ms  内存限制: 128 MB
提交: 194  解决: 57
[提交][状态][讨论版]

题目描述

帅气的男神有一棵n个节点的树(确性树形的有向树)。初始时刻，每个节点都有一个权值。

男神每次操作可以选择一个节点，然后给以这个节点为根的子树上的所有节点的权值加一或者减一。

男神想知道他最少多少次操作才可以把树上的权值全部变成0。

输入

第一行一个整数n，0<=n<=10^7。表示节点个数。

接下来n-1行，每行两个整数u，v。u是v的父节点。u，v<=n。

最后一行n个整数，从a1一直到an 。ai表示第i个节点的初始权值。|ai|<=10^9。

输出

输出最少的操作次数。

样例输入

3
1 2
1 3
1 1 1

样例输出

1

提示

来源

mdzz

[提交][状态][讨论版]