单点时限: 4.0 sec
内存限制: 512 MB
Cuber QQ 为前来参加舞会的朋友们准备了一棵摇钱树。摇钱树的枝头上挂着一些红包，舞会结束后，每位来宾可以折下一些树枝，拿走上面的红包。
Cuber QQ 不想让上面的红包都被朋友们拿走，所以舞会结束后，他将第一个来抢红包。Cuber QQ 想拿走尽可能多的红包，但是又不想显得过于吝啬（把整棵树抱走就太小气了）。所以他既不能剪掉太多的树枝，又要多拿点红包。
具体而言，给定一棵包含 $n$ 个节点的有根树，树根为 1 号节点。一部分节点上有红包，红包点的集合为 $S$。你可以选取不超过 $k$ 棵不相交的子树。假设这些子树的并为 $T$，求最优解 $T$ 使得 $|S\cap T|/|S \cup T|$ 最大。输出这个最大值。
第一行包含两个正整数 $n$ 和 $k$ （$1 \le n \le 10^5, 1\le k \le 50$），分别表示节点个数和最多选取子树数量。
第二行包含 $n$ 个正整数 $a_i$。$a_i=0$ 表示第 $i$ 号节点上没有红包，$a_i=1$ 表示第 $i$ 号节点上挂着一个红包。我们保证至少有一个 $a_i=1$。
接下来 $n-1$ 行，每行包含两个正整数 $u,v$，表示节点 $u$ 和 $v$ 之间存在一条边。
输出两个整数 $p,q$，使 $p/q$ 表示 $|S\cap T|/|S \cup T|$ 的最大值。要求 $p,q$ 互质。当 $p=0$ 时输出 0 1。
5 2 0 1 1 0 0 1 2 2 3 2 4 3 5
1 2
5 2 0 1 1 0 0 1 2 2 3 1 4 4 5
1 1