P5220 Agent’s Information Flow

$\text{TYM}$ is an agent. The country where $\text{TYM}$ lives is being invaded, and he is given a mission: to deliver information between cities.

The country where $\text{TYM}$ lives has $n$ cities, numbered $1,\dots,n$, connected by $n - 1$ bidirectional roads. It is guaranteed that there is a unique simple path between any two cities. Also, each city has an information flow rate $a_i$. $\text{TYM}$ needs to perform a total of $m_0$ missions. Each mission gives two cities $s,t$, and is carried out as follows: At the first moment, he starts from city $s$ and moves along the simple path between $s$ and $t$ to reach $t$, moving to the next city in each time unit. Every time he arrives at a city, he sends that city’s information flow $a_i$ to every city on the route he passes through. We agree that at the same moment he arrives at a city, he also sends that city’s information flow to itself. We define the value of a city as the product of all information flows received by that city. For each mission, compute the sum of the values of the cities on the simple path from $s$ to $t$, modulo $20924$. In addition, unfortunately, because the invaders are also acting at the same time, between his missions, some $a_i$ may change. The total number of missions plus the number of times an $a_i$ is changed is $m$.

The first line contains two integers $n,m$. The second line contains $n$ integers; the $i$-th integer represents the information flow rate $a_i$ of city $i$. The next $n - 1$ lines each contain two integers $u,v$, indicating that there is a bidirectional road between $u$ and $v$. The next $m$ lines each describe a mission or an update event: - In the form `Q s t`, meaning $\text{TYM}$ performs a mission from $s$ to $t$. - In the form `C x k`, meaning the invaders’ action makes $a_x \rightarrow a_x + k$.

For each mission, output the total sum of information flow received by the cities on the route.

**Constraints:** For $20\%$ of the testdata, $1 \leq n,m \leq 2000$. For an additional $20\%$ of the testdata, $a_i=2$, and there are no update operations. For an additional $20\%$ of the testdata, the roads connect $i$ to $i+1$. For $100\%$ of the testdata, $1 \leq n,m \leq 10^5, 1 \leq a_i \leq 20923$. **Sample Explanation:** For the first query, $1 \cdot 2 \cdot 3 \cdot 4 \cdot 5 + 2 \cdot 3 \cdot 4 \cdot 5 + 3 \cdot 4 \cdot 5 + 4 \cdot 5 + 5 = 325$. Update: $a_1 = 1 + 2 = 3$. For the second query, $3 \cdot 2 \cdot 3 \cdot 4 \cdot 5 + 2 \cdot 3 \cdot 4 \cdot 5 + 3 \cdot 4 \cdot 5 + 4 \cdot 5 + 5 = 565$. Translated by ChatGPT 5