3153: 小W算树
内存限制：256 MB
时间限制：1.000 S
评测方式：文本比较
命题人：
提交：1
解决：1
题目描述
投我以木桃，报之以琼瑶~ 小 W 给小 M 送了一棵满二叉树，小 M 很高兴，于是送给小 W 一棵 1 为根节点，叶子节点 挂满爱心的有根树。 每个节点都有一个爱心值， 叶节点爱心值为叶节点爱心数， 其余节点爱心值为以它为根 的子树所有叶子节点爱心数之和。 然而， 这样一棵树是脆弱的， 只有每个非叶节点所有孩子的爱心值相等， 才能茁壮成长。 小 W 只能忍痛割爱，摘下一些叶子节点的爱心（但是不可以摘成负数） 。 试求最少摘下多少爱心，这棵树就能茁壮生长。
输入
第一行一个整数 N，树的节点个数。 第二行 N 个正整数，表示每个节点的爱心数，保证只有叶子节点爱心数大于 0。 接下来 N-1 行，每行 2 个整数 S,T，表示 S 和 T 节点之间有连边。
输出
一行一个整数，最少摘下的爱心数。
样例输入 复制
6
0 0 12 13 5 6
1 2
1 3
1 4
2 5
2 6样例输出 复制
6提示
【 数据规模 】 对于 15%的数据：1<=N<=10。 对于 30%的数据：对于边 S,T，S+1<>T 的边不超过三条。 对于 50%的数据：1<=N<=1000。 对于 100%的数据：1<=N<=100000,1<=爱心数<=2^30。