5039. 摇钱树

单点时限: 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。

样例

Input
5 2
0 1 1 0 0
1 2
2 3
2 4
3 5
Output
1 2
Input
5 2
0 1 1 0 0
1 2
2 3
1 4
4 5
Output
1 1

11 人解决,27 人已尝试。

28 份提交通过,共有 122 份提交。

7.0 EMB 奖励。

创建: 1 年,2 月前.

修改: 1 年,2 月前.

最后提交: 3 月,3 周前.

来源: N/A

题目标签