{"problem":{"name":"[NOI2023] 贸易","description":{"content":"近年来，A 国的商贸发展迅猛，但国内的道路建设却跟不上步伐，明显成为了人们贸易往来的限制，管理者为此费尽了心思。 具体而言，A 国共有 $2^n-1$ 个城市，其中 $1$ 号城市为首都。对于所有的非首都城市 $i$，都有一条**单向**道路从城市 $i$ 出发，到达城市 $\\lfloor \\frac{i}{2} \\rfloor$。为方便起见，称这样的道路为“第一类道路”，称城市 $\\lfloo","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":1500,"memory_limit":524288},"difficulty":{"LuoguStyle":"P6"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP9481"},"statements":[{"statement_type":"Markdown","content":"近年来，A 国的商贸发展迅猛，但国内的道路建设却跟不上步伐，明显成为了人们贸易往来的限制，管理者为此费尽了心思。\n\n具体而言，A 国共有 $2^n-1$ 个城市，其中 $1$ 号城市为首都。对于所有的非首都城市 $i$，都有一条**单向**道路从城市 $i$ 出发，到达城市 $\\lfloor \\frac{i}{2} \\rfloor$。为方便起见，称这样的道路为“第一类道路”，称城市 $\\lfloor \\frac{i}{2} \\rfloor$ 为城市 $i$ 的“上级城市”。\n\n除此之外，还有 $m$ 条**单向**道路，设其中第 $i$ 条道路从城市 $u_i$ 出发，到达城市 $v_i$，这样的道路都有一个特殊性质：从城市 $v_i$ 出发，沿着第一类道路不断向“上级城市”走去，最终总能走到城市 $u_i$。称这样的道路为“第二类道路”。\n\n每一条道路都有相应的长度值。由此，对于 A 国的任意两个城市 $x$ 和 $y$，都可以计算出从城市 $x$ 出发，沿道路走到城市 $y$，所经过的道路的长度之和的最小值，将这一数值记为 $dist(x,y)$。但由于 A 国的道路建设存在严重缺陷，从城市 $x$ 出发可能根本到达不了城市 $y$，此时定义 $dist(x,y)=0$。同时一个城市出发到自己是不需要经过任何道路的，因此定义 $dist(x,x)=0$。\n\n现在管理者希望计算出这些 $dist(x,y)$ 的值，以便合理衡量人们贸易往来的便捷程度。但由于 A 国的城市数量太多，将这些值一一列出的工作量太大，因此管理者只希望求出所有 $dist(x,y)$ 值之和，也就是 $\\sum_{x=1}^{2^n-1}{\\sum_{y=1}^{2^n-1}{dist(x,y)}}$，并希望请你来帮忙。\n\n## Input\n\n输入的第一行包含两个正整数 $n$ 和 $m$。\n\n输入的第二行包含 $2^n-2$ 个正整数，第 $i$ 个数 $a_i$ 表示从城市 $i+1$ 出发, 到达城市 $\\lfloor \\frac{i+1}{2} \\rfloor$ 的“第一类道路”的长度。\n\n接下来的 $m$ 行，每行包含三个正整数 $u,v,w$，描述了一条从城市 $u$ 到城市 $v$ 的“第二类道路”, 其长度为 $w$。\n\n## Output\n\n输出一行一个正整数，表示对应的答案。由于答案可能很大, 你只需要输出模 $998244353$ 意义下的答案即可。\n\n[samples]\n\n## Note\n\n**【数据范围】**\n\n对于所有测试数据保证：$2 \\le n \\le 18$，$1 \\le m \\le 2 ^ n$，$1 \\le u, v \\le 2 ^ n - 1$，$1 \\le a_i, w \\le 10 ^ 9$。\n\n::cute-table{tuack}\n\n| 测试点编号 | $n$ | $m$ | 是否有特殊性质 |\n| :---: | :---: | :---: | :---: |\n| $1\\sim 2$ | $=8$ | $\\le 256$ | 否 |\n| $3\\sim 4$ | $=9$ | $\\le 512$ | ^ |\n| $5\\sim 8$ | $=12$ | $\\le 4,096$ | ^ |\n| $9$ | $=16$ | $\\le 10$ |  ^|\n| $10$ | ^ | $\\le 50$ | ^ |\n| $11$ | ^ | $\\le 100$ | ^ |\n| $12$ | ^ | $\\le 65,536$ | 是 |\n| $13\\sim 15$ | ^ | ^ | 否 |\n| $16\\sim 17$ | $=18$ | $\\le 262,144$ | 是 |\n| $18\\sim 20$ | ^ | ^ | 否 |\n\n特殊性质：保证每一条“第二类道路”都是从首都（城市 $1$）出发。","is_translate":false,"language":"English"}],"meta":{"iden":"LGP9481","tags":["2023","NOI","O2优化"],"sample_group":[["2 1\n2 1\n1 2 2","8"],["见附件中的 trade/trade2.in。","见附件中的 trade/trade2.ans。"],["见附件中的 trade/trade3.in。","见附件中的 trade/trade3.ans。"],["见附件中的 trade/trade4.in。","见附件中的 trade/trade4.ans。"]],"created_at":"2026-03-03 11:09:25"}}