{"problem":{"name":"「TFOI R1」Tree Home","description":{"content":"有一个由 $n - 1$ 条**带权无向边**连接成的有 $n$ 个节点的树，每个节点都有它对应的**编号**以及**权值** $v_{i}$，整棵树的根节点为编号为 $1$ 的节点。 令 $f(a, b, c) = (a - b) \\times \\left[a^2 + b^2 + a \\times b + 3 \\times c \\times (a + b + c)\\right]$，其中 $a,","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":1000,"memory_limit":262144},"difficulty":{"LuoguStyle":"P4"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP9704"},"statements":[{"statement_type":"Markdown","content":"有一个由 $n - 1$ 条**带权无向边**连接成的有 $n$ 个节点的树，每个节点都有它对应的**编号**以及**权值** $v_{i}$，整棵树的根节点为编号为 $1$ 的节点。\n\n令 $f(a, b, c) = (a - b) \\times \\left[a^2 + b^2 + a \\times b + 3 \\times c \\times (a + b + c)\\right]$，其中 $a,b,c$ 可以为任意整数。同时用 $d_i$ 表示 $i$ 到根节点的每条边的**边权**之和。\n\n现在天才 Z 要进行 $T$ 次询问，每次询问给定四个正整数 $l_{1},r_{1},l_{2},r_{2}$，你要从**编号**在区间 $[l_{1}, r_{1}]$ 和 $[l_{2}, r_{2}]$ 的点中各选择一个点 $p$ 和 $q$，当然你选择的两个点需要保证 $p \\neq q$。用 $r$ 表示 $p$ 和 $q$ 的最近公共祖先，要使得 $|f(d_{p} - d_{r}, d_{q} - d_{r}, d_{r})| + |v_{p} - v_{q}|$ 的值最大，而你需要对每次询问输出这个最大值。\n\n## Input\n\n第一行输入两个正整数 $n$ 和 $T$，表示这棵树的节点个数以及询问次数。\n\n第二行输入 $n$ 个整数，第 $i$ 个数表示编号为 $i$ 的节点的权值。\n\n接下来 $n - 1$ 行，每行输入三个整数 $u,v,w$，表示节点 $u$ 到节点 $v$ 之间有一条边权为 $w$ 的无向边。\n\n接下来 $T$ 行，每行输入四个整数 $l_{1},r_{1},l_{2},r_{2}$，表示一次询问（意义如题面所述）。\n\n## Output\n\n输出 $T$ 行，每行输出一个整数，表示每次询问的答案。\n\n[samples]\n\n## Background\n\n阳光开朗大男孩天才 Z 今天要向蕉太狼表白力！\n\n众所周知，蕉太狼是一个很可爱的女孩纸。\n从前的天才 Z 总是担心因为自己表白失败而受到别人的嘲笑。但是今天，天才 Z 就要做出自己一生中最重要的一件事，那就是真诚地表白，无论后果如何。\n\n出乎意料，蕉太狼其实也喜欢着天才 Z！\n\n天才 Z 开心得像个 0#。\n\n但是没过多久，天才 Z 就被甩力，原因蕉太狼发现天才 Z 对自己的闺蜜有非分之想。\n\n天才 Z 拿出了自己的树状家谱，问候起了自己的祖宗们。\n\n## Note\n\n#### 样例解释\n\n对于第一次询问，我们在两个区间分别取 $4$ 号点和 $6$ 号点即可得出答案 $19211$。\n\n对于第二次询问，两个区间都只能取一个节点，所以答案为 $3$。\n\n#### 数据范围\n\n**本题采用捆绑测试**。\n\n- Subtask 1（5 points）：$1 \\leqslant n, T \\leqslant 10$。\n- Subtask 2（10 points）：$1 \\leqslant n, T \\leqslant 100$。\n- Subtask 3（30 points）：$1 \\leqslant n, T \\leqslant 3000$。\n- Subtask 4（55 points）：无特殊限制。\n\n对于所有数据，$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$，保证树中最大深度不超过 $100$。\n\n**注意：两个区间 $[l_{1}, r_{1}]$ 和 $[l_{2}, r_{2}]$ 可能有重合部分。**","is_translate":false,"language":"English"}],"meta":{"iden":"LGP9704","tags":["线段树","O2优化","ST 表"],"sample_group":[["7 2\n5 1 7 12 5 9 6\n1 2 5\n3 1 1\n6 2 9\n4 6 14\n7 6 4\n5 2 10\n2 4 5 7\n1 1 3 3","19211\n3"]],"created_at":"2026-03-03 11:09:25"}}