P9704 "TFOI R1" Tree Home

The sunny and cheerful genius boy Z is going to confess his love to Jiao Tailang today! As everyone knows, Jiao Tailang is a very cute girl. In the past, genius Z always worried that he would be laughed at if his confession failed. But today, genius Z is going to do the most important thing in his life: confess sincerely, no matter what the result is. Unexpectedly, Jiao Tailang also likes genius Z! Genius Z is as happy as a 0#. But not long after that, genius Z got dumped. The reason is that Jiao Tailang found out that genius Z had improper thoughts about her best friend. Genius Z pulled out his tree-shaped family tree and started greeting his ancestors.

There is a tree with $n$ nodes connected by $n - 1$ **weighted undirected edges**. Each node has its corresponding **index** and **weight** $v_{i}$. The root of the whole tree is the node with index $1$. Let $f(a, b, c) = (a - b) \times \left[a^2 + b^2 + a \times b + 3 \times c \times (a + b + c)\right]$, where $a, b, c$ can be any integers. Also, let $d_i$ denote the sum of the **edge weights** on the path from node $i$ to the root. Now genius Z will make $T$ queries. In each query, four positive integers $l_{1}, r_{1}, l_{2}, r_{2}$ are given. You need to choose one node $p$ from the nodes whose **indices** are in the interval $[l_{1}, r_{1}]$, and choose one node $q$ from the nodes whose **indices** are in the interval $[l_{2}, r_{2}]$. Of course, the two chosen nodes must satisfy $p \neq q$. Let $r$ be the lowest common ancestor of $p$ and $q$. You need to maximize the value of $|f(d_{p} - d_{r}, d_{q} - d_{r}, d_{r})| + |v_{p} - v_{q}|$, and output this maximum value for each query.

The first line contains two positive integers $n$ and $T$, representing the number of nodes in the tree and the number of queries. The second line contains $n$ integers. The $i$-th number is the weight of the node with index $i$. The next $n - 1$ lines each contain three integers $u, v, w$, indicating that there is an undirected edge with weight $w$ between nodes $u$ and $v$. The next $T$ lines each contain four integers $l_{1}, r_{1}, l_{2}, r_{2}$, indicating one query (with the meaning described above).

Output $T$ lines. Each line contains one integer, representing the answer to each query.

#### Sample Explanation For the first query, we can take node $4$ from the first interval and node $6$ from the second interval, obtaining the answer $19211$. For the second query, each interval can only choose one node, so the answer is $3$. #### Constraints **This problem uses bundled testdata.** - Subtask 1 (5 points): $1 \leqslant n, T \leqslant 10$. - Subtask 2 (10 points): $1 \leqslant n, T \leqslant 100$. - Subtask 3 (30 points): $1 \leqslant n, T \leqslant 3000$. - Subtask 4 (55 points): no special restrictions. For all data, $1 \leqslant n, T \leqslant 2 \times 10^5$, $0 \leqslant |w| \leqslant 25$, $1 \leqslant v_{x} \leqslant 10^9$, $1 \leqslant l_{1} \leqslant r_{1} \leqslant n$, $1 \leqslant l_{2} \leqslant r_{2} \leqslant n$. It is guaranteed that the maximum depth of the tree does not exceed $100$. **Note: the two intervals $[l_{1}, r_{1}]$ and $[l_{2}, r_{2}]$ may overlap.** Translated by ChatGPT 5