P9481 [NOI2023] Trade

In recent years, Country A’s commerce has grown rapidly, but the construction of domestic roads has failed to keep up, which has clearly become a restriction on people’s trade activities. The administrators have put a lot of effort into this. Specifically, Country A has a total of $2^n-1$ cities, where city $1$ is the capital. For every non-capital city $i$, there is a **directed** road starting from city $i$ and going to city $\lfloor \frac{i}{2} \rfloor$. For convenience, call such roads “Type-1 roads”, and call city $\lfloor \frac{i}{2} \rfloor$ the “parent city” of city $i$. In addition, there are $m$ **directed** roads. Suppose the $i$-th road starts from city $u_i$ and goes to city $v_i$. Such roads have a special property: starting from city $v_i$ and repeatedly moving along Type-1 roads to the “parent city”, you can always eventually reach city $u_i$. Call such roads “Type-2 roads”. Each road has a corresponding length. Therefore, for any two cities $x$ and $y$ in Country A, we can compute the minimum possible sum of road lengths along a route that starts from city $x$ and follows roads to reach city $y$. Denote this value by $dist(x,y)$. However, due to serious flaws in Country A’s road system, it may be impossible to reach city $y$ from city $x$. In this case, define $dist(x,y)=0$. Also, traveling from a city to itself requires no roads, so define $dist(x,x)=0$. Now the administrators want to compute these values $dist(x,y)$ in order to reasonably measure how convenient trade is. But because there are too many cities, listing all these values one by one would be far too much work. Therefore, they only want the sum of all $dist(x,y)$, i.e. $\sum_{x=1}^{2^n-1}{\sum_{y=1}^{2^n-1}{dist(x,y)}}$, and they ask you to help.

The first line contains two positive integers $n$ and $m$. The second line contains $2^n-2$ positive integers. The $i$-th number $a_i$ denotes the length of the “Type-1 road” starting from city $i+1$ and going to city $\lfloor \frac{i+1}{2} \rfloor$. The next $m$ lines each contain three positive integers $u,v,w$, describing a “Type-2 road” from city $u$ to city $v$, with length $w$.

Output one line with one positive integer, the corresponding answer. Since the answer may be very large, you only need to output it modulo $998244353$.

**Constraints** For all testdata, it is guaranteed that: $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$. ::cute-table{tuack} | Test Point ID | $n$ | $m$ | Whether There Is a Special Property | | :---: | :---: | :---: | :---: | | $1\sim 2$ | $=8$ | $\le 256$ | No | | $3\sim 4$ | $=9$ | $\le 512$ | ^ | | $5\sim 8$ | $=12$ | $\le 4,096$ | ^ | | $9$ | $=16$ | $\le 10$ | ^ | | $10$ | ^ | $\le 50$ | ^ | | $11$ | ^ | $\le 100$ | ^ | | $12$ | ^ | $\le 65,536$ | Yes | | $13\sim 15$ | ^ | ^ | No | | $16\sim 17$ | $=18$ | $\le 262,144$ | Yes | | $18\sim 20$ | ^ | ^ | No | Special property: It is guaranteed that every “Type-2 road” starts from the capital (city $1$). Translated by ChatGPT 5