C. 摇钱树 - 2023 年 “图森未来杯” 全国高校程序设计网络邀请赛

仪表盘所有提交榜单题解

单点时限: 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 \leq n \leq 10^{5}, 1 \leq k \leq 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

Output

1 2

Input

Output

1 1

NaN

比赛状态发生变化，点 OK 刷新。

OK

2023 年 “图森未来杯” 全国高校程序设计网络邀请赛