P7159 「dWoi R1」Sweet Fruit Chocolate

[事情来源 ……](https://www.bilibili.com/video/BV19Z4y1K7dH) 我们的东条妈妈在残害了梦野之后，还想继续她的事业，残害可怜的最原。她发现最原很喜欢吃甜甜的巧克力，另外还有一种东西叫做西西弗水果，他富含营养但没那么好吃，因此，她想把这些巧克力淋在西西弗水果上。

东条把想淋的巧克力做成了一个巧克力喷泉树。巧克力喷泉树是一棵 $n$ 个节点的树。每个节点都有一个西西弗水果。对于每一个节点 $u$，你有两种选择：你可以在节点 $u$ 放置 $a_u$ 个水果，也可以一个水果都不放。然后，东条会在根节点往下淋巧克力汁。节点 $u$ 给最原带来的营养值是 $u$ 及其子树中所放置的西西弗水果的数量。东条想要知道，对于所有 $2^n$ 个放水果方案，最原所获得的营养值之和的总和是多少。答案对 $998244353$ 取余。 树的根节点为 $1$。

无

无

#### 样例 1 解释 用 $S$ 表示选中状态 - $S=000$ 贡献 $0$ - $S=001$ 贡献 $1$ - $S=010$ 贡献 $2$ - $S=011$ 贡献 $3$ - $S=100$ 贡献 $6$ - $S=101$ 贡献 $7$ - $S=110$ 贡献 $8$ - $S=111$ 贡献 $9$ #### 数据规模与约定 对于 $20\%$ 的数据，满足 $n\le 20$。 对于另外 $30\%$ 的数据，满足 $u=v-1$。 对于 $100\%$ 的数据，满足 $2\le n\le 10^6$，$1 \le a_i \le 10^9$。