4004. 喵星人集会

【题目描述】

现在有一颗n个点的树,其中某些点有一个喵星人.

现在他们要到某个地方进行集会,但是肯定不能都聚到一个点,因为放不下- -.

事实上,一个点还是只能容纳一只喵星人。

但是他们要尽可能靠近,也就是说：任意两只喵星人之间的路径上不能存在一个没有喵星人的点.

但是现在它们显然还没有这样的靠近.

每一个喵星人都可以从原来所处的位置移动到另一个位置,消耗的体力为两个位置之间的路径的边数.

现在你要让某些喵星人移动到另外的位置,使得他们尽可能靠近.在此前提下使得所有喵星人消耗的体力之和尽可能小.

注意的是,你不用考虑喵星人之间的相互影响.

【输入格式】

第一行一个整数n,表示树上的点数.

第二行一个长度为n的01串,若第i位为1则表示标号为i点开始时有一只喵星人.

接下来n − 1行,每行两个整数u, v,表示标号为u的点与标号为v的点之间有一条无向边.

【输出格式】

如存在一种合法的移动方法,输出一行一个整数,表示所有喵星人花费的体力值之和最小值.

否则输出除了QwQ之外的任意一个卖萌表情.

【样例输入】

6
001101
1 2
2 3
3 4
2 5
1 6

【样例输出】

2

【数据规模与约定】

对于20%的数据,保证喵星人的数目≤ 3.

对于50%的数据,n ≤ 20，保证喵星人的数目≤ 8.

对于100%的数据,1 ≤ n ≤ 50,1 ≤喵星人的数目≤ n。