3935. 净土裁断

【题目背景】

「昔日多情的樱花，如今已作墨色。待到雷声沉郁的寂然之刻，方晓渺渺泡影之梦将觉。」

「剃除俗世芜杂的执妄，只为扭转生灭轮回的羁缠。不为人所真正理解，亦不屑为人所 看破…将军殿下她，实在是一个很矛盾的人。」——狐斋宫

【题目描述】

雷军，稻妻全土毋容置疑的统治者。担负着「御建鸣神主尊大御所」之威名，许稻妻民 众以亘古不变之「永恒」。

雷军一边唱着稻妻最火的歌曲《Are you OK》，一边在稻妻的土地上随机游走。雷军将 通过稻妻上的传送锚点进行随机游走，传送锚点的关系构成一个树形结构。

具体来说, 在传送锚点 $u$ 的每个单位时间内，雷军将会有 $p_u$ 的概率留在原地, 有 $1−p_u$ 的概率等概率的向相邻的点移动，直到移动到 $1$ 号点才停下。

为了追求永恒地随机游走，雷军现在询问身在狐斋宫的你，从每个点出发直至停下，所 花费的时间的 $k$ 次方的期望, 对 $998244353$ 取模。

【输入格式】

第一行两个整数 $n$ 和 $k$，含义如题目所示。

接下来 $n−1$ 行，每行两个整数 $u,v$，代表一条树边。

接下来一行 $n − 1$ 个整数，第 $i$ 个 $p'_{i+1}，p_{i+1} =\frac{p'_{i+1}}{10^6}$ 代表留在原地的概率。

【输出格式】

输出 $n−1$ 行，第 $i$ 输出从 $i + 1$ 号点出发直至停下，所花费的时间的 $k$ 次方的期望, 对

$998244353$ 取模。

【样例输入】

3 1
1 2
2 3
0 0

【样例输出】

3
4

【数据规模与约定】

对于 100% 的数据，保证 $nk \le 10^7, 1 \le n,k \le 10^5, 0 \le p_i \lt 10^6$

【来源】

在此键入。