{"problem":{"name":"[HUSTFC 2023] 广义线段树","description":{"content":"对于任意长度为 $n$ 的序列 $a$，可以基于 $a$ 建立一个广义线段树。广义线段树是一个有 $(2n-1)$ 个节点的带权二叉树，对于每个编号为 $p$ 的节点，都有两个属性 $L_p$ 和 $R_p$，表示其维护的区间为 $[L_p,R_p]$，同时其权值 $M_p =\\prod_{i=L_p}^{R_p}a_i$ 。另外，广义线段树还满足如下性质： - 所有编号为 $p\\in [n,2n","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":{"LuoguStyle":"P5"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP9775"},"statements":[{"statement_type":"Markdown","content":"对于任意长度为 $n$ 的序列 $a$，可以基于 $a$ 建立一个广义线段树。广义线段树是一个有 $(2n-1)$ 个节点的带权二叉树，对于每个编号为 $p$ 的节点，都有两个属性 $L_p$ 和 $R_p$，表示其维护的区间为 $[L_p,R_p]$，同时其权值 $M_p =\\prod_{i=L_p}^{R_p}a_i$ 。另外，广义线段树还满足如下性质：\n- 所有编号为 $p\\in [n,2n-1]$ 的节点是叶节点，同时 $L_p = R_p = p + 1 - n$。\n- 所有编号为 $p\\in [1,n-1]$ 的节点是非叶节点，其必定有左儿子 $X_p$ 和右儿子 $Y_p$，且 $p < X_p < Y_p$。节点 $p$ 维护的区间为左右儿子维护区间之并，且保证维护区间连续。形式化地，有 $R_{X_p}=L_{Y_p}-1$，且 $L_p=L_{X_p}$，$R_p=R_{Y_p}$。\n\n例如，下面是一个基于 $n=4$ 的序列 $a=\\{1, 2, 3, 4\\}$ 建立的广义线段树（节点内整数对 $(p,M_p)$ 分别表示编号和权值）。可以发现，广义线段树的形态并不唯一。\n\n![1](https://cdn.luogu.com.cn/upload/image_hosting/de71i68l.png)\n\n对这个广义线段树而言：\n- $[L_7, R_7] = [4, 4]$，故 $M_7 = a_4$\n- $[L_6, R_6] = [3, 3]$，故 $M_6 = a_3$\n- $[L_5, R_5] = [2, 2]$，故 $M_5 = a_2$\n- $[L_4, R_4] = [1, 1]$，故 $M_4 = a_1$\n- $[L_3, R_3] = [L_4, R_5] = [1, 2]$，故 $M_3 = a_1 \\times a_2$\n- $[L_2, R_2] = [L_3, R_6] = [1, 3]$，故 $M_2 = a_1 \\times a_2 \\times a_3$\n- $[L_1, R_1] = [L_2, R_7] = [1, 4]$，故 $M_1 = a_1 \\times a_2 \\times a_3 \\times a_4$\n\n分别给定长度为 $n$ 的序列 $a$，$b$ 以及节点数为 $(2n-1)$ 的广义线段树 $T$ 的形态（即每个节点的左右儿子编号），然后你需要执行 $n$ 次操作，第 $i$ 次操作为将 $a_i$ 变成 $a_i\\times b_i$。\n\n每次操作结束后，你需要基于修改后的序列 $a$ 建立与 $T$ 形态相同的广义线段树，并求出所有节点的权值和，即 $\\sum_{i=1}^{2n-1}M_i$。由于结果可能会非常大，你只需要求出其对 $998\\,244\\,353$ 取模后的值。\n\n## Input\n\n第一行包含一个整数 $n\\ (1\\le n\\le 5\\cdot 10^5)$，表示序列 $a$ 和 $b$ 的长度。\n\n第二行包含 $n$ 个整数，其中第 $i$ 个整数定义为 $a_i\\ (1 \\le a_i < 998\\,244\\,353)$。\n\n第三行包含 $n$ 个整数，其中第 $i$ 个整数定义为 $b_i\\ (1 \\le b_i < 998\\,244\\,353)$。\n\n接下来 $n-1$ 行，其中第 $i$ 行包含两个整数 $X_i,Y_i\\ (i