{"problem":{"name":"Random Tree Distance","description":{"content":"There is an integer sequence $A = (A_2,A_3,\\ldots,A_N)$. Also, for an integer sequence $P=(P_2, P_3, \\ldots ,P_N)$ where $1 \\leq P_i \\leq i-1$ for each $i$ $(2 \\leq i \\leq N)$, define the weighted tre","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"arc195_e"},"statements":[{"statement_type":"Markdown","content":"There is an integer sequence $A = (A_2,A_3,\\ldots,A_N)$. Also, for an integer sequence $P=(P_2, P_3, \\ldots ,P_N)$ where $1 \\leq P_i \\leq i-1$ for each $i$ $(2 \\leq i \\leq N)$, define the weighted tree $T(P)$ with $N$ vertices, rooted at vertex $1$, as follows:\n\n*   A rooted tree where, for each $i$ $(2 \\leq i \\leq N)$, the parent of $i$ is $P_i$, and the weight of the edge between $i$ and $P_i$ is $A_i$.\n\nYou are given $Q$ queries. Process them in order. The $i$\\-th query is as follows:\n\n*   You are given integers $u_i$ and $v_i$, each between $1$ and $N$. For each of the possible $(N-1)!$ sequences $P$, take the tree $T(P)$ and consider the distance between vertices $u_i$ and $v_i$ in this tree. Output the sum, modulo $998244353$, of these distances over all $T(P)$. Here, the distance between two vertices $u_i$ and $v_i$ is the sum of the weights of the edges on the unique path (not visiting the same vertex more than once) that connects them.\n\n## Constraints\n\n*   $2 \\leq N \\leq 2 \\times 10^5$\n*   $1 \\leq Q \\leq 2 \\times 10^5$\n*   $1 \\leq A_i \\leq 10^9$\n*   $1 \\leq u_i < v_i \\leq N$\n*   All input values are integers.\n\n## Input\n\nThe input is given from Standard Input in the following format:\n\n$N$ $Q$\n$A_2$ $A_3$ $\\ldots$ $A_N$\n$u_1$ $v_1$\n$u_2$ $v_2$\n$\\vdots$\n$u_Q$ $v_Q$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"arc195_e","tags":[],"sample_group":[["3 2\n1 1\n1 2\n1 3","2\n3\n\n*   If $P = (1,1)$, then in the tree $T(P)$, the distance between vertices $1$ and $2$ is $1$, and the distance between vertices $1$ and $3$ is $1$.\n*   If $P = (1,2)$, then in the tree $T(P)$, the distance between vertices $1$ and $2$ is $1$, and the distance between vertices $1$ and $3$ is $2$.\n\nTherefore, the total distance between vertices $1$ and $2$ over all $T(P)$ is $2$, and the total distance between vertices $1$ and $3$ over all $T(P)$ is $3$."],["2 1\n100\n1 2","100"],["9 6\n765689282 93267307 563699854 951829154 801512848 389123318 924504746 596035433\n3 8\n2 5\n5 8\n2 9\n8 9\n5 7","55973424\n496202632\n903509579\n343265517\n550981449\n68482696\n\nRemember to take the sum modulo $998244353$."]],"created_at":"2026-03-03 11:01:14"}}