G-魔法树_牛客小白月赛79

时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

祝愿参加这赛季ICPC/CCPC的你我均能取得理想成绩，魔法树祝你好运~

长途有一棵魔法树，树中包含 $n$ 个点，编号为 $1$ ~ $n$ ，其中每一个结点都富含能量值。

现在大魔术师长途要开始施展魔法啦！他要砍掉树的任意多条边（可能 $0$ 条，可能 $1$ 条，可能更多）。当各个连通块中的能量值总和奇偶性都相同（即均为奇数或者均为偶数）时，魔法树会发生神秘反应，彻底释放出它的能量！

连通块的定义：若结点 $p_1$ 能通过某些树边到达结点 $p_2$ ，结点 $p_2$ 能通过某些树边到达结点 $p_1$ ，则称 $p_1$ 和 $p_2$ 处在同一个连通块当中

请问大魔法师长途有多少种方案使得魔法树能释放能量呢？
由于答案可能很大，你只需要输出答案对 $998244353$ 取模后的值即可
两种方案不同，当且仅当至少存在一条树边在一种方案中被砍，在另一种方案中没被砍

第一行一个整数，表示魔法树的结点数量
第二行输出个整数，其中第个数表示第号点的能量值为
接下来行，每行包含两个整数， ，表示结点和存在一条边
输入保证一定是一棵树

输出一个整数，表示大魔法师长途使得魔法树能释放能量的方案数。由于答案可能很大，你只需要输出答案对取模后的值

示例1

复制

复制

有以下三种情况各个连通块的奇偶性相同

示例2

复制

复制