### 问题描述 **"第 $114511$ 届蟠桃大会开始了！！！"** 蟠桃大会是天庭中最重要的节日，各路神仙齐聚一堂，只为品尝这三千年一熟的神果。每年，王母娘娘都会将最大的一颗蟠桃奖励给最聪明的神仙。 具体地说，王母娘娘会出一道题目，最快回答的神仙将会得到本年度的最大蟠桃。今年的题目如下： > 给定一颗有 $n$ 个节点的树，其中根节点编号为 $1$，第 $i$ 个点的颜色为 $s_i$，每个节点的颜色可能为白色或者黑色。请你计算任意满足以下条件的二元组 $(u,v)$ 的最近公共祖先的深度之和。 > > - $1 \leq u < v \leq n$。 > - $s_u \ne s_v$。 由于答案可能很大，需要对 $998244353$ 取模后输出。 齐天大圣孙悟空十分渴望得到这颗最大的蟠桃，奈何智商有限，请你帮帮他。 **注意：根节点的深度视为 $1$。** ### 输入格式 第一行输入一个整数 $n(1 \leq n \leq 10^5)$ 表示树的节点数量。 第二行输入一个长度为 $n$ 的字符串 $s(s_i \in[0,1])$，其中 $s_i$ 表示第 $i$ 个节点的颜色，若 $s_i=0$ 则表示白色，否则表示黑色。 接下来 $n-1$ 行，每行两个整数 $u,v(1 \leq u,v \leq n)$ 表示节点 $u,v$ 之间有一条边。保证给定的数据为一棵树。 ### 输出格式 输出一个整数表示答案，答案需要对 $998244353$ 取模后输出。 ### 输入样例 ```text 5 10011 1 2 2 3 2 4 1 5 ``` ### 输出样例 ```text 8 ``` #### 说明 对于样例给定的树如下图：