暂无测试数据。

给定一棵 $n$ 个节点的有根树，根为节点 $1$。

每一个节点都有一朵未开放的花，起初任意选择一朵花（只能选择一朵）将其开放，花费 $1$ 的费用。

然后你可以花费 $a$ 将已经开花的节点的父亲节点的花开放，也可以花费 $b$ 将 已经开花的节点的子节点的花开放。

某种情况下，令 $k$ 为当前开放的花的朵数，$c$ 为当前的总花费，求每一个 $k$ 所对应的最小的 $c$。

输入格式

输入共 $n$ 行。

第一行输入三个正整数 $n,a,b$。

接下来 $n-1$ 行每行输入两个正整数 $w_i,v_i$，表示树的一条边。

输出格式

输出共 $n$ 行，每行输出一个整数。

第 $i$ 行表示 $k=i$ 时最小的 $c$。

数据范围

对于 $30\%$ 的数据，$1\leq n,a,b\leq 10$。

对于另外 $30\%$ 的数据，$1\leq n\leq 10^3$。

对于所有数据，$1\leq n\leq 10^5$，$1\leq a<b\leq n^2$。

5 1 2
1 2
2 3
3 4
4 5

1
2
3
4
5

5 2 3
1 2
1 3
2 4
2 5

1
3
5
8
11