P3241 [HNOI2015] Opening a Shop

Kazami Yuuka has a good friend named Yakumo Yukari. They often watch the stars and the moon together, chatting from poetry and songs to life philosophy. Recently, they had a sudden idea to open a small shop in Gensokyo to do business and make some money. This idea is certainly great, but they also found a problem: where to open the shop and which group of customers to target. Interestingly, the map of Gensokyo is a tree. There are $n$ places in total, numbered from $1$ to $n$, connected by $n-1$ weighted edges. Each place is inhabited by a youkai, and the age of the youkai at place $i$ is $x_i$. Youkai are relatively quiet, so they do not want to be adjacent to too many youkai. Therefore, the degree of every vertex in this tree is at most $3$. Interests change naturally with age. For example, our $18$-year-old girls Yuuka and Yukari may prefer cute things. Yuuka discovered through research that a youkai’s interests basically depend only on age. So Yuuka plans to choose a place $u$ (a vertex id), and open a shop at $u$ targeting youkai whose ages are between $L$ and $R$ (that is, ages greater than or equal to $L$ and less than or equal to $R$). It is possible that place $u$ is far from these youkai. Thus, Yuuka wants to know the sum of distances from all youkai with ages in $[L, R]$ to $u$ (the distance from a youkai to $u$ is the sum of edge weights along the path from its place to $u$). Yuuka calls this the convenience value of the shop plan. They have not yet decided where to open the shop, and Yukari has prepared many plans. For each plan, what is the convenience value?

- The first line contains three space-separated integers $n$, $Q$, and $A$, representing the size of the tree, the number of shop plans (queries), and the upper bound of youkai ages. - The second line contains $n$ space-separated integers $x_1, x_2, \ldots, x_n$. Here $x_i$ is the age of the youkai at place $i$, satisfying $0 \le x_i \lt A$. (Age can be $0$, for example, a newborn youkai has age $0$.) - The next $n-1$ lines each contain three space-separated integers $a$, $b$, and $c$, indicating that there is an edge of weight $c$ ($1 \le c \le 1000$) between vertices $a$ and $b$, where $a$ and $b$ are vertex ids. - The next $Q$ lines each contain three space-separated integers $u$, $a$, and $b$. For each of these $Q$ lines, compute $L$ and $R$ from $a$, $b$, and $A$. This specifies the query “open a shop at place $u$, targeting youkai with ages in $[L, R]$, and ask for the convenience value.” - For the first query (the $1$-st line), compute: $L=\min(a \bmod A, b \bmod A)$, $R=\max(a \bmod A, b \bmod A)$. - For the $2$-nd to the $Q$-th queries, suppose the convenience value obtained from the previous query is $ans$. Then compute: $L=\min((a+ans) \bmod A, (b+ans) \bmod A)$, $R=\max((a+ans) \bmod A, (b+ans) \bmod A)$.

For each plan, output one line containing the convenience value.

Constraints: $n \le 1.5 \times 10^5$, $Q \le 2 \times 10^5$. For all testdata, $A \le 10^9$. Translated by ChatGPT 5