「PMOI-3」子树
题目背景
分割线下有形式化题面,可以配合食用。
题目描述
b6e0 有一棵树,树上第 $i$ 个点有价值 $a_i$。每条边长度为 $1$。
b6e0 会选择一个节点作为根节点。设这个节点为 $r$。然后,b6e0 会圈定一个节点的整个子树作为他的领地,设这个子树的根节点为 $u$。此时,树上的每个节点会给 b6e0 带来一些收益。在领地子树的根节点为 $u$ 的情况下,节点 $x$ 带来的收益 $f(x,u)$ 定义如下:
1. 当 $x$ 在 $u$ 的子树中时,它的收益为它父亲节点的收益加上它本身的价值 $a_x$;
2. 当 $x$ 不在 $u$ 的子树中时,它的收益为:与它相邻的节点中,与 $u$ 距离(到 $u$ 的简单路径长度)比 $x$ 到 $u$ 的距离远的节点,这些节点的收益**对 $998244353$ 取模**的最大值,再乘上 $a_x$。
在根节点为 $r$ 的情况下,定义以 $u$ 为子树的收益 $W(u)$ 为所有节点的 $f$ 值和。
当然,b6e0 有许多种选择根节点的方案。定义选 $r$ 为根节点的收益 $C(r)$ 为对于所有 $u$,以 $u$ 为子树的收益($W(u)$)的和。对于每一个节点 $r$,求 $C(r)$。
---
形式化题面:
给你一棵有 $n$ 个节点的树,第 $i$ 个节点有点权 $a_i$,每条边的长度为 $1$。当根节点为 $r$ 时:
设 $F(x)$ 表示 $x$ 的父亲节点,特殊地,$F(r)=0$;$D(x,y)$ 表示 $x$ 到 $y$ 的简单路径的长度,特殊地,对于所有 $x$,$D(x,x)=0$;$A_x$ 表示 $x$ 的子树中的节点(包括 $x$ 本身)组成的集合,即 $A_x=\{y\mid D(x,y)=D(F(x),y)-1\}$,特殊地,$A_r=\{1,2,\cdots,n\}$;$B_x$ 表示与 $x$ 相邻的节点组成的集合,即 $B_x=\{y\mid D(x,y)=1\}$。
定义 $f(x,u)$:
$$f(x,u)=\begin{cases}f(F(x),u)+a_x&x\in A_u\\a_x\cdot\max_{y\in B_x,D(y,u)>D(x,u)}\{f(y,u)\bmod 998244353\}&x\not\in A_u\end{cases}$$
特殊地,对于所有 $x$,$f(0,x)=0$;在 $x\not\in A_u$ 的情况中,若对于所有 $y\in B_x$,都有 $D(y,u)\le D(x,u)$,则 $f(x,u)=a_x$。
定义节点 $u$ 的分数 $W(u)=\sum_{v=1}^nf(v,u)$。
定义节点 $r$ 的收益 $C(r)$ 表示以 $r$ 为根时,$\sum_{i=1}^nW(i)$ 的值。
对于每一个节点 $r$,求 $C(r)$。
**所有 $C(r)$ 对 $998244353$ 取模。**
输入输出格式
输入格式
第一行输入一个正整数 $n$ 表示这棵树的节点数。
第二行输入 $n$ 个整数,第 $i$ 表示节点 $i$ 的点权 $a_i$。
下面 $n-1$ 行,每行输入两个正整数 $u,v$,表示节点 $u$ 与节点 $v$ 之间有一条边。
输出格式
输出 $n$ 行,第 $i$ 行输出一个正整数表示节点 $i$ 的收益 $C(i)$ **对 $998244353$ 取模**的值。
输入输出样例
输入样例 #1
6
7 2 5 100 1 5
1 3
3 4
1 2
4 5
4 6
输出样例 #1
67562
29930
75168
76888
63243
63283
说明
【样例解释】
样例中的树如下图:
![](https://cdn.luogu.com.cn/upload/image_hosting/bs02n466.png)
例如在 $r=1$,$u=5$ 时,$f(2,u)=a_2=2$,$f(1,u)=a_1\cdot f(2,u)=14$,$f(3,u)=a_3\cdot f(1,u)=70$,$f(6,u)=a_6=5$,$f(4,u)=a_4\cdot\max\{f(3,u),f(6,u)\}=7000$,$f(5,u)=f(4,u)+a_5=7001$。
【数据范围】
- Subtask1(10pts):$n\le200$,$a_i\le 10^3$;
- Subtask2(20pts):$n\le10^3$;
- Subtask3(20pts):树为一条链;
- Subtask4(20pts):存在一个节点,使得它的度数为 $n-1$;
- Subtask5(30pts):无特殊限制。
对于 $100\%$ 的数据,$1\le n\le5\times10^5$,$1\le a_i\le10^9$。