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$。