U138701.零昼回声：双相树谱

题目背景

公元 3147 年，人类在“零昼带”发现了一种无法被传统坐标描述的物质结构——回声树。

一棵回声树由若干枚记忆晶核与无向的相位通道组成。由于零昼带中的空间不会形成环，每两枚晶核之间都存在唯一的一条相位路径，因此整套结构恰好是一棵树。

每枚晶核 $i$ 同时携带两种彼此正交的相位：

• 昼相强度 $a_i$；
• 夜相强度 $b_i$。

当两枚不同晶核 $u,v$ 同时被激活时，它们会产生一种非常特殊的“双相交换干涉”。

若二者在回声树上的距离为 $d$，则它们对第 $d$ 层回声频谱产生的贡献为

$$a_u b_v+a_v b_u.$$

研究人员并不关心某一对晶核，而是希望一次性恢复整棵回声树的完整距离频谱：

对于每个可能的距离 $d$，求所有距离恰好为 $d$ 的无序点对产生的总干涉强度。

由于零昼带中的相位数值极大，所有结果均在模数 $998244353$ 下计算。

---

题目描述

给定一棵包含 $n$ 个点的无根树。

点 $i$ 有两个整数权值 $a_i,b_i$。

对于两个不同的点 $u,v$，定义它们的双相干涉值为

$$I(u,v)=a_u b_v+a_v b_u.$$

设 $\operatorname{dist}(u,v)$ 表示 $u,v$ 在树上的边数距离。

对于每个 $d=1,2,\ldots,n-1$，定义

$$R_d= \sum_{\substack{1\le u<v\le n\\ \operatorname{dist}(u,v)=d}} \left(a_u b_v+a_v b_u\right).$$

请计算所有的

$$R_1,R_2,\ldots,R_{n-1}.$$

所有答案对 $998244353$ 取模。

第一行一个整数 $n$，表示回声树中的晶核数量。

第二行 $n$ 个整数

$$a_1,a_2,\ldots,a_n.$$

第三行 $n$ 个整数

$$b_1,b_2,\ldots,b_n.$$

接下来 $n-1$ 行，每行两个整数 $u,v$，表示点 $u$ 与点 $v$ 之间存在一条无向边。

保证给出的图是一棵树。

输出一行 $n-1$ 个整数：

$$R_1,R_2,\ldots,R_{n-1}.$$

所有答案均对 $998244353$ 取模。

当 $n=1$ 时，输出一个空行。

样例解释

距离为 $1$ 的点对为

$$(1,2),(1,3),(3,4),(3,5).$$

它们的贡献分别为

$$1\times4+2\times5=14,$$

$$1\times3+3\times5=18,$$

$$3\times2+4\times3=18,$$

$$3\times1+5\times3=18.$$

因此

$$R_1=14+18+18+18=68.$$

距离为 $2$ 的所有点对总贡献为

$$R_2=80.$$

距离为 $3$ 的所有点对总贡献为

$$R_3=42.$$

树中不存在距离为 $4$ 的点对，因此

$$R_4=0.$$

---

数据范围

对于所有测试数据：

$$1\le n\le 2\times10^5,$$

$$0\le a_i,b_i<998244353.$$

保证输入图为一棵树。