题目描述Description

在洛克王国的广袤大陆上，精灵训练师们通过不断收服和培养宠物来提升自己的实力。某位传奇训练师麾下的精灵们形成了一个树状的传承体系：他以自己为根结点，直接培养了一批核心精灵，这些核心精灵又各自指导着其他精灵，如此向下延续。

王国研究者发现，在一个精灵分支（以某只精灵为根的子树）内部，成员之间的力量值差异会直接影响它们的羁绊同步率。为此，研究者定义了 羁绊分歧度：

对于一支精灵分支，其羁绊分歧度等于该分支内所有精灵两两力量值之差的绝对值之和。

分歧度越大，说明成员之间力量差距越悬殊，在进行团队合作时越不容易产生共鸣；分歧度越小，成员力量越接近，羁绊越深厚。

现在，给出整个传承树的脉络以及每只精灵的力量值，请你对每一个精灵分支计算其羁绊分歧度。由于数值可能很大，请将结果对 998244353 取模后输出。

给定一棵以 1 号精灵为根的有根树，结点 i 对应一只精灵，其力量值为 a_i（1 \le a_i \le 10^9）。

对于树上任意一个子树 T(u)（即以 u 为根的子树），设其包含的精灵集合为 S(u)，定义该子树对应的精灵分支的 羁绊分歧度 为: D(u) = \sum_{\substack{x, y \in S(u)\\ x \neq y}} |a_x - a_y|

即考虑所有无序精灵对 \{x,y\}（x \neq y），计算力量值之差的绝对值再求和。

你需要对每个 u = 1, 2, \dots, n 输出 D(u) \bmod 998244353 的值。

输入格式Input

第一行一个正整数 n，表示精灵的总数。
第二行 n 个正整数 a_1, a_2, \dots, a_n，依次表示编号为 1 \sim n 的精灵的力量值。
接下来 n-1 行，每行两个整数 u, v，表示在传承树中 u 与 v 之间有一条直接传承关系（无向边）。输入保证所有边构成一棵树，且根结点为 1。

输出格式Output

一行 n 个整数，第 i 个整数表示 D(i) \bmod 998244353，即编号为 i 的精灵所带领分支的羁绊分歧度模 998244353 的值。

样例Sample

提示Hint

样例解释

传承关系：精灵 1 与精灵 2、3 直接相连，精灵 2 与精灵 4 直接相连，以 1 为根形成树。
- 以精灵 1 为根的分支包含全体精灵 \{1,2,3,4\}，力量值 \{2,5,1,4\}。排序后为 \{1,2,4,5\}，所有无序对差的绝对值之和为
|1-2|+|1-4|+|1-5|+|2-4|+|2-5|+|4-5| = 1+3+4+2+3+1 = 14。
- 以精灵 2 为根的分支包含 \{2,4\}，力量值 \{5,4\}，|5-4|=1。
- 精灵 3 和精灵 4 各自的分支仅一只精灵，分歧度为 0。

数据范围

• 1 \le n \le 2 \times 10^5，1 \le a_i \le 10^9。

关于递归深度的特别说明

本题递归深度可能引发栈溢出。为了避免因递归过深而 RE，你可以参考下面这种方式：

int main() {
    int size(64 << 20);  // 64 MB
    __asm__("movq %0, %%rsp\n" :: "r"((char*)malloc(size) + size));
    // your code ...
    exit(0);   // 必须使用 exit 结束程序，不能通过 return 返回
}

出题Author

来源Source