代码

// [o18f_] 第三层 RMQ：把稀疏表的高层（1.0 MB）换成「超级块前后缀 + 超级块级稀疏表」（合计 350 KB）。
// ===== REFERENCES =====
// [1] duck.ac 用户 **saffah_codex_6a_agg3**，提交 **#120380** <https://duck.ac/submission/120380>
//     （252.738102 ms，本题实时榜首 / 非本账号最快）= 本文件正文的逐字节基座。其相对 #120374 的增量 =
//     `[PAIR-SIMD]` 端点对解析器（`ni_pair`）；#120374 = 本账号 **#107978** 正文 + `[LV-OUT]`（`TNode` 32B→24B）。
//     **上述三件的引用链与逐行 diff 说明见本文件下方 `[o18e_]` 段（原样保留，未改一字）。**
//     本发**只改** `rmq_query` / 稀疏表构造那一段（下文 [o18f-R3]），正文其余部分与 #120380 逐字节相同。
// [2] 本账号 **saffah_cc_v41_agg1**，提交 **#120441** <https://duck.ac/submission/120441>（253.020719 ms）
//     = #120380 的逐字节复刻（实测 253.0207 ↔ 252.7381，逐位复刻成立的旁证），即本发的直接前身。
// [3] 本工作区 `problems/noi18e/notes.md` 的 `[o18e_ 席]` 节（行级 cachegrind 账）与 `[o18f_ 席]` 节（本发消融账）。
//     **只引用其结论与数字，未复制其中任何代码。**
// ===== 思路 =====
// 【口径（tools/exact.py noi18e 现读）】mine = 253.020719（#120441）· T = 252.738102（#120380）
//   · 严支 `0.99*T+1µs = 250.211721` ⇒ 缺口 **2.808998 ms（1.110%）**。
// 【定位（本席消融账；本机 `os.wait4` rusage 交错 min-of-N，用例 b18w_tc9m.txt）】
//   · 摘掉 `calc` 内全部 LCA-RMQ：**−12.46%**（RMQ 的总价）
//   · 只摘「块内」那半（短程扫描 + `rmq_pref/rmq_suf`）：**−1.79%**
//   · 只摘「稀疏表」那半：**−9.79%** ⇒ **稀疏表 = RMQ 总价的 78%**，靶子在它的两次随机取点上，不在块内。
// 【被否掉的方案（负读数，留档）】把 `rmq_pref/suf/rmq_st` 改存 **u16 结点号 + `dep_` 比较**（表 2.30 MB→1.15 MB）
//   ⇒ **+12.8%（更慢）**：打包 `(dep<<16|node)` 的 u32 比较是免费的，而"取结点再查 `dep_`"的**间接依赖链**很贵
//   ⇒ **"u16 存结点"这条常见建议在本族被实测关闭**（与 §八.3 的猜测相反）。
// 【本发 `[o18f-R3]`：三层块状 RMQ（只改分组，不改比较序）】
//   原结构：块(4 位置) 的 `rmq_pref/rmq_suf` → 对 25003 个块最小值的 **15 层稀疏表（1.5 MB）**。
//   新结构：`rmq_pref/rmq_suf` 不变；块级再加两层 ——
//     ① 超级块（`RMQS=8` 个块 = 32 位置）内的**块前缀/后缀** `bpref/bsuf`（2×100 KB）；
//     ② 对 3126 个超级块最小值的**稀疏表** `bsp`（12 层 ×3126×4 = 150 KB）；
//     ③ 只在「块区间跨超级块」时走 ②，否则仍走降为 **4 层**（`RMQLVL=4`）的原稀疏表。
//   ⇒ 长程查询的两次随机取点从 **1.5 MB（L2 未命中）** 变为 200 KB/150 KB 的 **L2/L1 命中**；
//     所有取值仍是同一个 `rmq_pick`（打包 u32），**逐位等价**，未引入任何新的比较语义。
// 【为什么不是更激进的块大小】`RMQS` 取 4/8/16 都测过：16 时跨超级块的查询太少（读数≈不变），
//   4 时新增的两层取数抵消了局部性收益；**8 是拐点**。
// 【闸门（交前全跑；`-DLOCAL_TEST` 才是本族唯一读 stdin 的构建）】
//   ① `e18t_gate.sh o18e_lv8.cpp o18f_cand.cpp`：`rt.py`/`chainrt.py`/`czerort.py`/`mixc0rt.py` 各 **300 例 0 失配**
//      + 样例 + **3 份大用例（18.9 MB / 11.7 MB / 10.3 MB）逐字节相同** ⇒ **PASS**；
//   ② `g++ -O1 -fsanitize=address` 跑大用例：**无越界**（首版把"除 8"误写成 `>>8`，**只有 ASAN 抓到**：
//      小用例全绿 ⇒ 再次印证本族"必须跑 ASAN/大用例闸门"）；
//   ③ 判题机同款 `g++-9` 的 `-DLOCAL_TEST` 档编译 rc=0。不带 `-DLOCAL_TEST` 的那档在本机因 glibc 版本的
//      `__libc_start_main` 重复定义而链接失败，**但 #120441 那份已 AC 的源在本机是同一个错** ⇒ 环境性，非本发引入。
// 【本机读数（交错 min/med，三轮独立 A/B，用例 b18w_tc9m.txt）】−1.66/−2.95 · −5.60/−5.41 · −1.66/−2.95
//   ⇒ 三轮**同向为负**，量级 1.7~5.6%。
// 【可证伪判据】判题机 < **253.020719** 即为正；≤ **250.211721** 即达标（本题转绿）。
// [o18e_] 采用对手最新件 #120380（= 本账号 #107978 正文 + 对手两刀）—— 逐字采用，正文一字未改。
// ===== REFERENCES =====
// [1] duck.ac 用户 **saffah_codex_6a_agg3**，提交 **#120380** <https://duck.ac/submission/120380>
//     （252.738102 ms，本题实时榜首 / 非本账号最快）。**本文件正文 = #120380 逐字节**。其相对 #120374 的增量已逐行核实
//     （`work/o18e_tmp/o18e_d2.diff`，43 行，全部为一处新增 + 三处调用点替换）：
//     **`[PAIR-SIMD]` 端点对解析器 `ni_pair(int&,int&)`**：一次 16 B `_mm_loadu_si128` + `_mm_movemask_epi8(cmpgt('0',v))`
//     求两个数段的 `ctz` 边界 ⇒ `_mm_shuffle_epi8` 查 **1024 B 的 `PSH` 表**（按 (la,lb) 取一个 16 B 模式）+
//     `_mm_maddubs_epi16`/`_mm_madd_epi16`/`_mm_packs_epi32` 三段定点合并完成**打包十进制转换**（一次产出 x,y 两数）；
//     **`v` 值（cost）仍走标量 `nll()`**（其自述"Retain scalar reads for wide costs and input tails"），尾部/越界回落到 `ni()`。
//     调用点：`solve_group` 的查询环 `ni_pair(x,y)`、边环 `ni_pair(a,b)`、`solve_chain` 的查询环。
// [2] duck.ac 用户 **saffah_codex_6a_agg3**，提交 **#120374** <https://duck.ac/submission/120374>
//     （261.538574 ms）= #120380 的基座；#120374 本身 = 本账号 #107978 正文 + `[LV-OUT]`（`TNode` 32 B → 24 B，
//     叶子缓存值改存 `item_lv[pool[o].e]`）。逐行 diff 见 `work/o18e_tmp/o18e_d1.diff`。
// [3] duck.ac 用户 **saffah_cc_v41_agg1**（本账号），提交 **#107978** <https://duck.ac/submission/107978>
//     （263.268692 ms）= 上述两件的共同基座（[E18S-C0]/[E18V-G2]/[E18V-SEQ] 等全在其正文里）。
//     本账号本席前一发 **#120428** <https://duck.ac/submission/120428>（261.530692 ms）= #120374 逐字节复刻（实测 261.5307
//     ↔ 对手 261.5386，**8 µs 内**，复刻逐位成立的旁证）。
// [4] 工作区 BRIEF §2.18.349（先算"抄下来能到哪"）/ §2.18.355（FAQ 缓存几何：L1d 32 KB · L2 256 KB 4-way · L3 6 MB）/
//     §2.18.346（"uop 数削减"四件套：查表替代重算 —— 本刀 = 其第 4 条的极端形态）。
// ===== 思路 =====
// 【口径（tools/exact.py noi18e 现读，2026-10-02 18:49）】mine = 261.530692（#120428）· **T = 252.738102（#120380）**
//   · 严支 `0.99*T+1µs = 250.211721` ⇒ 缺口 **11.318971 ms（4.33%）**；而**本件本身 = 252.738102**
//   ⇒ 采用后缺口收到 **2.526381 ms（1.0%）**。★ **§2.18.349 判据：抄下来够吗？否**（252.738 > 250.212）
//   ⇒ 必须"抄 + 我们独有一刀"。
// 【本发 = 逐字采用 #120380】理由：① 该件**已被判题机接受**（榜首）⇒ 零编译/正确性风险；
//   ② 它是**对手在我方 #107978 正文上的两刀之和**（[LV-OUT] + [PAIR-SIMD]），而 [LV-OUT] 已在判题机上定价 −1.730 ms
//   （见 #120374 逐点：tc6 −3.328 · tc7 −3.499 · tc17 −3.052 · tc18 −2.148 · tc5 −1.730），
//   故 [PAIR-SIMD] 的定价 ≈ **#120374 → #120380 = −8.800472 ms（−3.37%）**（解析原占 Σ 的 ~16%，与 −3.4% 相容）。
//   两个数字都是**判题机原值**，不是我方不可移植的本机读数（§2.18.348 的"刀价基座相关"在此已核：基座 = 我方正文）。
// 【未做（时间盒到）】第三刀尚未落地；下一步见 `problems/noi18e/notes.md` 的 `[o18e_ 席]` 节：
//   本席新取的**行级 cachegrind 账**（`work/o18e_tmp/o18e_cg_a.out`，`-g` 重建）指出最大单块 = **RMQ 稀疏表族**
//   （行 142 取 sparse 表 106 727/276 532 = 39% 缺、行 129 的 pref/suf 61 625、行 128 dep_ 16 415 ⇒ 合计 24% 的 D1 读缺），
//   这正是 §八.3 未开采的"把 `rmq_st` 换形到 L2 量级"（±1 RMQ / u16 存结点）。
// 【可证伪判据】判题机 ≈ **252.738102** ⇒ 逐位复刻成立且无布局漂移；若明显优于 252.7 ⇒ 我方复刻另有 microarch 收益。
/* References:
[1] saffah_cc_v41_agg1, https://duck.ac/submission/107978.
Reused the tree, segment-tree merge, diameter-pair cache, and ordered item flow.
The source's inherited citations follow below; no separate license is declared.
Idea: Parse each pair of endpoint IDs with one 16-byte delimiter scan and
packed decimal conversion. Retain scalar reads for wide costs and input tails.
Move each leaf's cached pair value to an array keyed by its first selected
item. Active leaves have disjoint item sets, so their selected item IDs cannot
alias. After replacing a pair, store its value under the newly selected first
item. Internal nodes then need only 24 bytes instead of 32; the leaf cache is
bounded by the item count rather than the much larger node count.
Purpose: Test paired endpoint parsing together with the smaller node layout.
*/

// [e18v_] [E18V-SEQ] 主循环的"入口表 + 条目"改成**按遍历顺序排布的连续流**（单变量 = 布局）。
// ===== REFERENCES =====
// [1] duck.ac 提交 **#107754** <https://duck.ac/submission/107754>（278.829573 ms）—— 正文基底与其完整引用链（一字未动）。
// [2] 本账号 **#107936** <https://duck.ac/submission/107936>（278.278541 ms，现役最好件）= 同一基底 + `[E18V-G2]`
//     （删 `Item::g2`，它与 `w` 逐位相等）⇒ 本件 = **#107936 的正文** + 本发的布局改动。
//     对手现役最好件 **#107712** <https://duck.ac/submission/107712>（277.255441 ms）⇒ 严支靶 `0.99*T+1µs = 274.483887`。
// [3] 本工作区 BRIEF §2.19.889（**消融表 × 指令账 两表相除**）/ §2.19.853 · §2.19.809（足迹/工作集族）/
//     §2.19.793（红题下"发更慢件无害"）/ §2.19.802（闸门先验 rc + stdout 非空）。
// ===== 思路 =====
// 【口径】mine = 278.278541（#107936）· T = 277.255441（#107712）· 严支 274.483887 ⇒ 缺 **3.794654 ms（1.364%）** ✓
// 【本发的依据 = 本席自己量的两条前置事实】
//  ① **消融表 × 指令账**（§2.19.889；用例 = 代理用例 `b18w_tc9m.txt` 全 10 组，本机 min-of-2）：
//     `abl_base 0.30s` / **`abl_noins 0.09s`（−70%）** / `abl_nomerge 0.26s`（−18%）/ `abl_nolca 0.28s`（−12%）/`abl_nolg 0.31s`
//     而该子系统**只占 ~50% 指令**（ins 29% + merge 11% + leaf_combine 6.7% + wipe 3.8%）
//     ⇒ **时间份额 > 指令份额 ⇒ 瓶颈是访存延迟，不是发射** ⇒ 该打"改结构/换表示"✓
//  ② **归因探针**：把 `ins()` 里的 `itm[pt]` 冷随机取数换成常数（故意算错，只测成本）⇒ **0.23 → 0.17 s（−26%）** ✓
// 【本发（单变量 = 主循环两条流改连续）】
//   原实现：入口表 `path_entries[]` **按顶点号**分块，条目号 `pt` 是**查询序**（2i+1/2i+2）⇒ 主循环按 `ord_[]`
//   （逆先序）访问时，入口表与条目表都是散乱跳；而 `itm[pt]` 的取数是**冷随机**，还被插入链串行化 ✓
//   本发：① 计数排序的键改为"该顶点**在遍历序里的位置**" ⇒ 每个顶点的块就是遍历即将访问的那一块；
//        ② 散射时把**条目载荷**搬到它自己的下标（`itm2[j+1] = itm[ppt[e]]`）⇒ **条目号 = 入口下标**，
//           显式 id 数组 `ppt`（800 KB）整段消失；③ 主循环退化为 `pkey2[]`(2 B/项) + `itm2[]`(24 B/项) **两条连续流** ✓
//   ★ 语义不变：散射保持**稳定** ⇒ 顶点内插入次序与原来逐位相同 ⇒ 树状态与每个 `ans` 更新逐位相同 ✓
// 【闸门（全过）】① 判题机同款 `g++-9 9.3.0` **两种配置**都编译 rc=0：
//   `-DLOCAL_TEST`（本地 stdin 驱动）**与**判题机配置（**不加** `-DLOCAL_TEST`：走 `DI` 直接接口）✓
//   ★ 这一条是本席上一发**用汇编学到的教训**：本发的上一版把"分块读入"写在了 `#ifdef LOCAL_TEST` 的 `g_in` 上，
//     本地全绿而**判题机 Compile Error**（`size_t`/`memmove`/`g_in` 未声明）⇒ 本发**已完全去掉那一段**，
//     并把"判题机配置编译"列进闸门 ✓（详见 BRIEF 建议：现成 `e18t_gate.sh` 只编 `-DLOCAL_TEST` 一档）
//   ② `e18t_gate.sh`：4 个随机差分生成器各 **300 例 0 失配** + 样例 + 3 份大用例**逐字节相同** ⇒ **PASS** ✓
//   ③ `-DLOCAL_TEST` 运行 rc=0、stdout 非空 ✓
//   ★ 闸门救回的第二个真错（如实记录）：首版条目号从 0 起，而**池用 `e == 0` 当"空叶子"哨兵** ⇒ 同键对永不计算
//     ⇒ 小用例 3/300 失配（大用例反而全同）。修法 = 条目号偏移 +1（0 留给哨兵）✓
// 【本机读数（交替 min-of-3）】基座 0.25/0.27/0.23 s ↔ 本件 **0.22/0.22/0.23 s** ⇒ **−8~−18%** ✓
//   （另在 `e18s_c0big.txt` 上 0.10→0.09、`n18y_s2.txt` 上 0.14/0.15→0.11/0.12 ⇒ 三种用例形状同向 ✓）
// 【可证伪判据】判题机 < **278.278541** 即为正；≤ **274.483887** 即达标。
// ================
// ===== REFERENCES =====
// [1] duck.ac 用户 saffah_codex_6s_agg2，提交 **#107239** <https://duck.ac/submission/107239>（283.723198 ms = 本题实时 T / 榜首）
//     —— **本文件正文的逐字节基座**（工作副本 `problems/noi18e/work/e18s_rep_b.cpp`）。除本注释块与下文逐条标注的
//     两处改动外一字未改；#107239 自述所基于的 #106860 亦为本账号件，出处链完整。
// [2] duck.ac 用户 saffah_cc_v41_agg1（本账号），提交 **#107330** <https://duck.ac/submission/107330>（281.567193 ms）
//     —— 本发的 `[E18S-C0]` 那一行取自本账号该件（本人上一发，同一基座）。其逐点表给因果：
//     c=0 短路换来 tc7/8/9 的 −5.95/−9.95/−10.93 ms。
// [3] 题面 `problems/noi18e/statement.txt`（subtask 表：`c_i = 0` 的测试点；`0 ≤ c_i ≤ 1e9`、`0 ≤ v_i ≤ 1e10·n`）
//     与团队 `problems/noi18e/notes.md`（`e18_` 节：c0 的语义证明；`b18x_` 节：调用计数与剖面方法）。
//     **只引用结论与方法，未复制其中任何代码。**
// ======================
// ===== 思路 =====
// 【目的】压 `tc18`（当代 MAX，通用大点）。本发两处改动，都是"**删工作**"型、输出逐位不变。
//
// 【改动一 `[E18S-LV]`：把叶子结点的"配对值"缓存进池结点，删掉每次重算。】
//   `leafval(o)` 在 `ins`/`s2_ins` 的叶子尾段与 `merge_tr` 的 `merge_tr(l==r)`（`leaf_combine`）里被调用，
//   只要叶子不是单元素，它就要**重算一次 `calc(x,y)`（= 一次完整的 LCA-RMQ）**——而 `(x,y)` 在这三处
//   都**没有变化**（`e/f` 只在真的换对时才被改写）。
//   ★ 本席用**被读次数计数器**先给它定价（诊断件 `work/e18s_cnt.cpp`，**永不提交**，
//     代理用例 `b18w_tc9m.txt`，Σn=296,897 / Σm=485,750）：
//       `calc = 2,312,346` · `leafval = 1,224,111`（单元素 580,954 / **需 RMQ 的 643,157**）·
//       `ins_tail = 701,901` · `ins_new = 268,953` · `ins_empty = 0` · `leaf_combine = 261,105`
//     ⇒ **28% 的 `calc` 调用（= 28% 的 RMQ）是纯重算**。
//   实现：`struct TNode { i64 mf, mg, lv; u32 e, f; }`（**恰好 32 B**，池结点各占一条 cache line 的半边，
//   不变式 `lv == 原 leafval(o)`），三处维护：
//     · 新建叶子 / 叶子首次落项 ⇒ `lv = singval(pt)`（`singval` 就是原单元素分支的 `2*(itm[pt].w - dis_[itm[pt].v])`）；
//     · `ins`/`s2_ins` 尾段换对 ⇒ `lv = v`（**已经算出来的 `max(v1,v2)`，零额外代价**）；
//     · `leaf_combine` ⇒ 读 `item_lv[pool[a].e]/item_lv[pool[b].e]`，末尾 `item_lv[pool[a].e] = best`（**同样是已算出的值**）。
//   ★ 不变式成立的两个前提（都已核）：(1) `wipe` 只在 `l < K ≤ r` 时改写子指针 ⇒ **结点必为内点**，
//     叶子永远不会被它改写；(2) 叶子只由 `ins` 的 `pool[o].e = pool[o].f = pt` 创建 ⇒ **叶子恒非空**
//     （计数确认 `ins_empty = 0`），`leaf_combine` 的 `(rx,ry)` 也恒非零。
//     `pool` 由 24 B 涨到 32 B（+33% 足迹，实测判题机内存 19584→ 见读数），换来的是每次读 `lv` **一条同线取数**
//     替掉 2~5 次随机取数 + 一次 RMQ。
//
// 【改动二 `[E18S-C0]`：题面 `c_i = 0` 的组直接短路 `calc` 的 LCA 项。】
//   一组数据所有边权为 0 ⇒ `dis_[*] ≡ 0` ⇒ `lcadis(...) ≡ 0` ⇒ `calc(x,y) = itm[x].w + itm[y].w`（**逐位同值**，
//   被减项恒为 0，不是近似）。`g_c0` 在**逐组**读边时顺手求得；非 c=0 的组只多一条完全可预测的分支。
//
// 【闸门（交前全跑；`-DLOCAL_TEST` 才是本族唯一读 stdin 的构建）】
//   ① 手工最小用例 `printf '1\n2\n1 2 5\n1\n1 2 3\n'` ⇒ `F`；题面样例 ⇒ `1` / `F`（**非空断言**：
//      不加 `-DLOCAL_TEST` 时 `main` 走 `__libc_start_main` 拦截取数据块、不读 stdin ⇒ 空输出是假绿）；
//   ② `rt.py` 300 · `chainrt.py` 300 · `czerort.py`（**全 c=0 数据**）300 · `mixc0rt.py`（c=0 组与随机权重组**同文件混排**）300 ⇒ **全 0 mismatch**；
//   ③ 逐字节闸门：`b18w_tc9m.txt`（19 MB 全非零权）· `e18s_c0big.txt`（11.7 MB **全 c=0**）· `n18y_s2.txt`（S2，10 MB）与基座**逐字节相同**；
//   ④ 判题机同款编译（`-O2 -static -U_FORTIFY_SOURCE -std=c++17`，不带 `-DLOCAL_TEST`）通过。
// ================
#pragma GCC optimize("O3")
#pragma GCC target("arch=skylake")
#include <immintrin.h>
/* [E18T-O3] pragma pair; see header of the submission copy */
#ifdef LOCAL_TEST
#include <cstdio>
#endif
#ifdef DBG
#include <cstdio>
#endif
#if defined(LOCAL_TEST) || defined(DBG)
#include <cstdio>
#include <cstdlib>
#include <cstring>
typedef unsigned long long u64;
static char g_in[48 << 20];
static char g_out[8 << 20];
#else
typedef unsigned long long u64;
#endif

typedef long long i64;
typedef unsigned int u32;

#define MAXN 50005
#define MAXM 100005
#define MAXE 100005
#define MAXIT 200010
#define MAXPOOL 3600005
#define LG 18

static const i64 NINF = -(i64)1 << 60;

// ---------------- tree ----------------
static u32 head_[MAXN + 2];
static unsigned short eto[MAXE]; static u32 ew[MAXE];
static unsigned short par_[MAXN], dep_[MAXN], pre_[MAXN];
static i64 dis_[MAXN];
static unsigned short euler[2 * MAXN];
static u32 first_[MAXN];   // Euler POSITION (<=2n-1=100009) needs 17 bits: stays u32
// Sixteen-entry Euler blocks: packed depth+node prefix/suffix minima and
// a sparse table over the block minima, about 1.2 MB in total.
#define RMQB 4
#define RMQRS 2
#define RMQNB ((2 * MAXN + RMQB - 1) / RMQB)
/* [o18f-R3] Three-layer block RMQ.  Layer 1 = within-block prefix/suffix over Euler
   positions (unchanged, position indexed).  Layer 2 = prefix/suffix of block minima
   inside a SUPERBLOCK of RMQS blocks.  Layer 3 = sparse table over superblock minima.
   Layers 2+3 together are 268 KB and replace sparse levels 5..14 (1.0 MB); all picks
   stay on the SAME packed (dep<<16|node) values, so every combine is bit-for-bit the
   original -- only the grouping changes.  Ranges whose block span fits in one
   superblock still take the (now 5-level, 500 KB) low sparse, exactly as before. */
#define RMQS 8                       /* blocks per superblock (= 64 positions) */
#define RMQSS 3                       /* log2(RMQS): superblock = block >> RMQSS */
#define RMQLVL 4                      /* kept low sparse levels: k = 0..4 */
#define RMQNSB ((RMQNB + RMQS - 1) / RMQS)
static u32 rmq_pref[2 * MAXN], rmq_suf[2 * MAXN];
static u32 rmq_st[RMQLVL][RMQNB];
static u32 bsuf[RMQNB], bpref[RMQNB];
static u32 bsp[12][RMQNSB];
static inline u32 rmq_pack(u32 v) { return ((u32)dep_[v] << 16) | v; }
static inline u32 rmq_pick(u32 a, u32 b) { return a < b ? a : b; }
static inline u32 rmq_query(u32 l, u32 r) {
  if (l > r) { u32 z=l; l=r; r=z; }
  u32 bl=l>>RMQRS, br=r>>RMQRS;
  if (bl==br) {
    u32 z=rmq_pack(euler[l]);
    for (u32 j=l+1;j<=r;j++) z=rmq_pick(z,rmq_pack(euler[j]));
    return z;
  }
  u32 z=rmq_pick(rmq_suf[l],rmq_pref[r]);
  if (bl+1<br) {
    u32 L=bl+1, R=br-1, len=R-L+1;
    if ((L>>RMQSS)!=(R>>RMQSS)) {        /* straddles a superblock: layers 2+3 */
      z=rmq_pick(z,rmq_pick(bsuf[L],bpref[R]));
      u32 SL=(L>>RMQSS)+1, SR=(R>>RMQSS)-1;
      if (SL<=SR) {                      /* empty when the two are adjacent */
        u32 sl=SR-SL+1, k=31u-(u32)__builtin_clz(sl);
        z=rmq_pick(z,rmq_pick(bsp[k][SL],bsp[k][SR-(1u<<k)+1]));
      }
    } else {                             /* inside one superblock: low sparse, k<=4 */
      u32 k=31u-(u32)__builtin_clz(len);
      z=rmq_pick(z,rmq_pick(rmq_st[k][L],rmq_st[k][R-(1u<<k)+1]));
    }
  }
  return z;
}
static unsigned short ord_[MAXN];

static int g_c0;             // 1 <=> every c_i of this group is 0
static int g_chain;          // 1 <=> the tree is the literal chain 1-2-...-n

static inline int lca_of(int u, int v) {   // node identity, used once per path
  return (int)(rmq_query(first_[u],first_[v]) & 0xffffu);
}
// hot path: the callers only need dis[lca], never which node it is.  Takes the two
// Euler first-occurrence positions straight out of the item (no first_[] load).
static inline i64 lcadis(u32 fu, u32 fv) {
  return dis_[rmq_query(fu,fv) & 0xffffu];
}

// ---------------- items (32B, self-contained for cache) ----------------
struct Item { u32 v; u32 fv; i64 w, f2; };   // fv = first_[v]; w = dis[v] + w  [E18V-G2] g2 == w
static Item itm[MAXIT];
static Item itm2[MAXIT];   /* [E18V-SEQ] items in traversal order */
static u32 phead[MAXN + 2];
static u32 phead2[MAXN + 2];   /* [E18V-SEQ] indexed by traversal position */
static unsigned short pkey2[MAXIT];
static u32 ordpos_[MAXN + 2];
static u32 pkey[MAXIT], ppt[MAXIT];
struct PathEntry { u32 key, pt; };
static PathEntry path_entries[MAXIT];
static int g_key1;   /* 1 <=> every item's pkey == 1 (subtask S2) */

// ---------------- segment tree ----------------
// own (mf,mg) = max f2/g2 over the key range; e,f = children (leaf: item ids).
// 32B aligned => one node is always inside one cache line.
struct TNode { i64 mf, mg; u32 e, f; };
static i64 item_lv[MAXIT];   /* [E18S-LV] lv = value of the stored pair (leaves only) */
static TNode pool[MAXPOOL];
static u32 pool_n;
static i64 ans;

static inline i64 calc(int x, int y) {   // itm[].w already carries dis[v]
  /* [E18S-C0] all-zero edge weights => dis_[*] == 0 => the LCA term vanishes. */
  if (g_c0) return itm2[x].w + itm2[y].w;
  return itm2[x].w + itm2[y].w - 2 * lcadis(itm2[x].fv, itm2[y].fv);
}

static void pushup(u32 o) {
  u32 l = pool[o].e, r = pool[o].f;
  i64 f = NINF, g = NINF;
  if (l) { i64 x = pool[l].mf; if (x > f) f = x; x = pool[l].mg; if (x > g) g = x; }
  if (r) { i64 x = pool[r].mf; if (x > f) f = x; x = pool[r].mg; if (x > g) g = x; }
  pool[o].mf = f; pool[o].mg = g;
}

/* [E18S-LV] singleton pair value: leafval(o) for pool[o].e == pool[o].f == pt. */
static inline i64 singval(int pt) { return 2 * (itm2[pt].w - dis_[itm2[pt].v]); }
static inline i64 leafval(u32 o) { return item_lv[pool[o].e]; }

static void leaf_combine(u32 a, u32 b, i64 deep2) {
  int ax = (int)pool[a].e, ay = (int)pool[a].f;
  int bx = (int)pool[b].e, by = (int)pool[b].f;
  i64 best = NINF, cross = NINF;
  int rx = 0, ry = 0;
  { i64 v = item_lv[pool[a].e]; best = v; rx = ax; ry = ay; }
  { i64 v = item_lv[pool[b].e]; if (v > best) { best = v; rx = bx; ry = by; } }
  /* [K30] calc(x,y) is a pure read of (x,y) and each call below is an LCA-RMQ.  When a leaf
     holds a single item (the common case) ax==ay and/or bx==by, so 4 of the 6 calls are
     duplicates of a call already made with the SAME arguments in the SAME order: the guards
     skip only those.  Every surviving call, and every `v > best` / `v > cross` decision,
     is bit-for-bit the original. */
  if (ax) {
    if (bx) { i64 v = calc(ax, bx); if (v > best) { best = v; rx = ax; ry = bx; } if (v > cross) cross = v; }
    if (by && by != bx) { i64 v = calc(ax, by); if (v > best) { best = v; rx = ax; ry = by; } if (v > cross) cross = v; }
  }
  if (ay && ay != ax) {
    if (bx) { i64 v = calc(ay, bx); if (v > best) { best = v; rx = ay; ry = bx; } if (v > cross) cross = v; }
    if (by && by != bx) { i64 v = calc(ay, by); if (v > best) { best = v; rx = ay; ry = by; } if (v > cross) cross = v; }
  }
  if (pool[b].mf > pool[a].mf) pool[a].mf = pool[b].mf;
  if (pool[b].mg > pool[a].mg) pool[a].mg = pool[b].mg;
  pool[a].e = (u32)rx; pool[a].f = (u32)ry; item_lv[pool[a].e] = best;
  if (cross != NINF) { i64 t = cross - deep2; if (t > ans) ans = t; }
}

// Iterative insert.  With a node now storing its OWN range maxes, inserting one item
// changes every node on the root-to-leaf path by exactly max(old, f2) / max(old, g2) --
// so the recursion AND all 1.2M pushup calls in this path disappear.
static u32 ins(u32 o, int l, int r, int pos, int pt, i64 deep2) {
  i64 f2 = itm2[pt].f2, g2 = itm2[pt].w;   /* [E18V-G2] g2 == w */
  u32 root = o, *link = &root;
  int lo = l, hi = r;
  while (lo < hi) {
    if (!o) {
      o = ++pool_n;
      pool[o].e = 0; pool[o].f = 0;
      pool[o].mf = f2; pool[o].mg = g2;
      *link = o;
    } else {
      { i64 nf = pool[o].mf; nf = f2 > nf ? f2 : nf;
        i64 ng = pool[o].mg; ng = g2 > ng ? g2 : ng;
        pool[o].mf = nf; pool[o].mg = ng; }
    }
    int mid = (lo + hi) >> 1;
    if (pos <= mid) {
      u32 rc = pool[o].f;                    // sibling's right half is deeper
      if (rc) { i64 v = f2 + pool[rc].mg - deep2; if (v > ans) ans = v; }
      link = &pool[o].e; o = pool[o].e; hi = mid;
    } else {
      u32 lc = pool[o].e;                    // this item is the deeper one
      if (lc) { i64 v = pool[lc].mf + g2 - deep2; if (v > ans) ans = v; }
      link = &pool[o].f; o = pool[o].f; lo = mid + 1;
    }
  }
  if (!o) {                                  // leaf at lo == hi == pos, first item in it
    o = ++pool_n;
    pool[o].e = (u32)pt; pool[o].f = (u32)pt;
    pool[o].mf = f2; pool[o].mg = g2;
    item_lv[pool[o].e] = singval(pt);
    *link = o;
    return root;
  }
  if (f2 > pool[o].mf) pool[o].mf = f2;
  if (g2 > pool[o].mg) pool[o].mg = g2;
  u32 x = pool[o].e, y = pool[o].f;
  if (!x) { pool[o].e = pool[o].f = (u32)pt; item_lv[pool[o].e] = singval(pt); return root; }
  i64 v1 = calc(pt, (int)x), v2 = (x == y) ? v1 : calc(pt, (int)y);
  i64 v = v1 > v2 ? v1 : v2;
  { i64 t = v - deep2; if (t > ans) ans = t; }
  i64 v0 = item_lv[pool[o].e];
  if (v0 >= v1 && v0 >= v2) return root;
  if (v1 >= v2) pool[o].f = (u32)pt; else pool[o].e = (u32)pt;
  item_lv[pool[o].e] = v;
  return root;
}

static u32 merge_tr(u32 a, u32 b, int l, int r, i64 deep2) {
  if (!a) return b;
  if (!b) return a;
  if (l == r) { leaf_combine(a, b, deep2); return a; }
  int mid = (l + r) >> 1;
  u32 al = pool[a].e, ar = pool[a].f, bl = pool[b].e, br = pool[b].f;
  i64 amf0 = pool[a].mf, amg0 = pool[a].mg, bmf0 = pool[b].mf, bmg0 = pool[b].mg;
  { i64 am = al ? pool[al].mf : NINF;
    if (am != NINF) { i64 v = am + (br ? pool[br].mg : NINF) - deep2; if (v > ans) ans = v; }
    i64 bm = bl ? pool[bl].mf : NINF;
    if (bm != NINF) { i64 v = bm + (ar ? pool[ar].mg : NINF) - deep2; if (v > ans) ans = v; } }
  pool[a].e = merge_tr(al, bl, l, mid, deep2);
  pool[a].f = merge_tr(ar, br, mid + 1, r, deep2);
  pool[a].mf = amf0 > bmf0 ? amf0 : bmf0;
  pool[a].mg = amg0 > bmg0 ? amg0 : bmg0;
  return a;
}

// keys > K never occur (presence rule), so clearing key K is enough; but the range
// version below is equivalent and simpler to keep exact.
static u32 wipe(u32 o, int l, int r, int K) {
  if (!o || r < K) return o;
  if (l >= K) return 0;
  int mid = (l + r) >> 1;
  if (K <= mid) {
    u32 c0 = wipe(pool[o].e, l, mid, K);
    if (!c0) return 0;
    pool[o].e = c0; pool[o].f = 0;
    pool[o].mf = pool[c0].mf; pool[o].mg = pool[c0].mg;
    return o;
  }
  u32 c0 = pool[o].e;
  u32 c1 = wipe(pool[o].f, mid + 1, r, K);
  pool[o].f = c1;
  if (!c1) {
    if (!c0) return 0;
    pool[o].mf = pool[c0].mf; pool[o].mg = pool[c0].mg;
    return o;
  }
  i64 f = pool[c1].mf, g = pool[c1].mg;
  if (c0) { i64 x = pool[c0].mf; if (x > f) f = x; x = pool[c0].mg; if (x > g) g = x; }
  pool[o].mf = f; pool[o].mg = g;
  return o;
}

// ---------------- io ----------------
#ifdef LOCAL_TEST
static const unsigned char *ip_, *ie_;
static char *op_;
#else
struct DI {
  u64 abi;
  const char *s; u64 sn;
  char *o; u64 ol; u64 os;
  char *e; u64 el; u64 es;
  const char *IB; u64 IBl;
  char *OB; u64 OBl;
  u64 tsc;
} __attribute__((packed));
static DI *D;
static const unsigned char *ip_, *ie_;
static char *op_;
#endif

static inline i64 nll() {
  const unsigned char *p = ip_;
  while (*p <= ' ') p++;
  i64 v = 0;
  while (*p > ' ') { v = v * 10 + (i64)(*p - '0'); p++; }
  ip_ = p;
  return v;
}
static inline int ni() { return (int)nll(); }
static const unsigned char PSH[1024] __attribute__((aligned(16))) = {128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,1,128,128,128,128,128,128,128,128,128,128,128,128,128,128,1,2,128,128,128,128,128,128,128,128,128,128,128,128,128,1,2,3,128,128,128,128,128,128,128,128,128,128,128,128,1,2,3,4,128,128,128,128,128,128,128,128,128,128,128,1,2,3,4,5,128,128,128,128,128,128,128,128,128,128,1,2,3,4,5,6,128,128,128,128,128,128,128,128,128,1,2,3,4,5,6,7,128,128,128,128,128,128,128,0,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,0,128,128,128,128,128,128,128,2,128,128,128,128,128,128,128,0,128,128,128,128,128,128,2,3,128,128,128,128,128,128,128,0,128,128,128,128,128,2,3,4,128,128,128,128,128,128,128,0,128,128,128,128,2,3,4,5,128,128,128,128,128,128,128,0,128,128,128,2,3,4,5,6,128,128,128,128,128,128,128,0,128,128,2,3,4,5,6,7,128,128,128,128,128,128,128,0,128,2,3,4,5,6,7,8,128,128,128,128,128,128,0,1,128,128,128,128,128,128,128,128,128,128,128,128,128,128,0,1,128,128,128,128,128,128,128,3,128,128,128,128,128,128,0,1,128,128,128,128,128,128,3,4,128,128,128,128,128,128,0,1,128,128,128,128,128,3,4,5,128,128,128,128,128,128,0,1,128,128,128,128,3,4,5,6,128,128,128,128,128,128,0,1,128,128,128,3,4,5,6,7,128,128,128,128,128,128,0,1,128,128,3,4,5,6,7,8,128,128,128,128,128,128,0,1,128,3,4,5,6,7,8,9,128,128,128,128,128,0,1,2,128,128,128,128,128,128,128,128,128,128,128,128,128,0,1,2,128,128,128,128,128,128,128,4,128,128,128,128,128,0,1,2,128,128,128,128,128,128,4,5,128,128,128,128,128,0,1,2,128,128,128,128,128,4,5,6,128,128,128,128,128,0,1,2,128,128,128,128,4,5,6,7,128,128,128,128,128,0,1,2,128,128,128,4,5,6,7,8,128,128,128,128,128,0,1,2,128,128,4,5,6,7,8,9,128,128,128,128,128,0,1,2,128,4,5,6,7,8,9,10,128,128,128,128,0,1,2,3,128,128,128,128,128,128,128,128,128,128,128,128,0,1,2,3,128,128,128,128,128,128,128,5,128,128,128,128,0,1,2,3,128,128,128,128,128,128,5,6,128,128,128,128,0,1,2,3,128,128,128,128,128,5,6,7,128,128,128,128,0,1,2,3,128,128,128,128,5,6,7,8,128,128,128,128,0,1,2,3,128,128,128,5,6,7,8,9,128,128,128,128,0,1,2,3,128,128,5,6,7,8,9,10,128,128,128,128,0,1,2,3,128,5,6,7,8,9,10,11,128,128,128,0,1,2,3,4,128,128,128,128,128,128,128,128,128,128,128,0,1,2,3,4,128,128,128,128,128,128,128,6,128,128,128,0,1,2,3,4,128,128,128,128,128,128,6,7,128,128,128,0,1,2,3,4,128,128,128,128,128,6,7,8,128,128,128,0,1,2,3,4,128,128,128,128,6,7,8,9,128,128,128,0,1,2,3,4,128,128,128,6,7,8,9,10,128,128,128,0,1,2,3,4,128,128,6,7,8,9,10,11,128,128,128,0,1,2,3,4,128,6,7,8,9,10,11,12,128,128,0,1,2,3,4,5,128,128,128,128,128,128,128,128,128,128,0,1,2,3,4,5,128,128,128,128,128,128,128,7,128,128,0,1,2,3,4,5,128,128,128,128,128,128,7,8,128,128,0,1,2,3,4,5,128,128,128,128,128,7,8,9,128,128,0,1,2,3,4,5,128,128,128,128,7,8,9,10,128,128,0,1,2,3,4,5,128,128,128,7,8,9,10,11,128,128,0,1,2,3,4,5,128,128,7,8,9,10,11,12,128,128,0,1,2,3,4,5,128,7,8,9,10,11,12,13,128,0,1,2,3,4,5,6,128,128,128,128,128,128,128,128,128,0,1,2,3,4,5,6,128,128,128,128,128,128,128,8,128,0,1,2,3,4,5,6,128,128,128,128,128,128,8,9,128,0,1,2,3,4,5,6,128,128,128,128,128,8,9,10,128,0,1,2,3,4,5,6,128,128,128,128,8,9,10,11,128,0,1,2,3,4,5,6,128,128,128,8,9,10,11,12,128,0,1,2,3,4,5,6,128,128,8,9,10,11,12,13,128,0,1,2,3,4,5,6,128,8,9,10,11,12,13,14};
static inline void ni_pair(int &aa,int &bb) {
  const unsigned char *p=ip_;u32 a,b;
  if(p+17>ie_){aa=ni();bb=ni();return;}
  ++p;
  __m128i v=_mm_loadu_si128((const __m128i *)p);
  unsigned mask=(unsigned)_mm_movemask_epi8(_mm_cmpgt_epi8(_mm_set1_epi8('0'),v));
  unsigned la=(unsigned)__builtin_ctz(mask), end=(unsigned)__builtin_ctz(mask&(mask-1));
  unsigned lb=end-la-1;
  __m128i x=_mm_shuffle_epi8(_mm_and_si128(v,_mm_set1_epi8(15)),_mm_load_si128((const __m128i *)(PSH+(la*8+lb)*16)));
  x=_mm_maddubs_epi16(x,_mm_set1_epi16(0x010a));
  x=_mm_madd_epi16(x,_mm_set1_epi32(0x00010064));
  x=_mm_madd_epi16(_mm_packs_epi32(x,x),_mm_set1_epi32(0x00012710));
  a=(u32)_mm_cvtsi128_si32(x);b=(u32)_mm_extract_epi32(x,1);p+=end;
ip_=p;aa=a;bb=b;
}
static inline void pc(char c) { *op_++ = c; }
static inline void pll(i64 v) {
  char t[24]; int q = 0;
  if (v < 0) { pc('-'); v = -v; }
  if (!v) t[q++] = '0';
  while (v) { t[q++] = (char)('0' + (int)(v % 10)); v /= 10; }
  while (q) pc(t[--q]);
}


// ---------------- chain specialist (a_i = b_i - 1) ----------------
#define MAXS 131072
static u32 cw_[MAXN + 2];
static i64 dis2_[MAXN + 2];
static u32 ox[MAXM], oy[MAXM], ord2[MAXM + 1], cstart[MAXN + 3];
static i64 ow[MAXM];
static i64 trC[2 * MAXS];
// trN has exactly two operations: "increase the value at p" and "max over [p, n]".  Reversing
// the index turns the suffix query into a prefix max, so a Fenwick max tree gives both in
// ~log/2 probes instead of the segment tree's ~2*log (query) / ~log (update); the per-group
// clear also drops from 2*base to bnN = n+1.
static i64 bitN[MAXS + 2];
static int bnN;
static inline i64 asuf_qry(int p) {
  i64 res = NINF;
  for (int i = bnN - p; i > 0; i -= i & -i) { i64 t = bitN[i]; if (t > res) res = t; }
  return res;
}
static inline void asuf_upd(int p, i64 v) {
  for (int i = bnN - p; i <= bnN; i += i & -i) { if (bitN[i] >= v) break; bitN[i] = v; }
}

static i64 range_max(const i64 *tr, int l, int r, int base) {
  i64 res = NINF;
  if (l > r) return res;
  int lo = base + l, hi = base + r + 1;
  while (lo < hi) {
    if (lo & 1) { if (tr[lo] > res) res = tr[lo]; lo++; }
    if (hi & 1) { hi--; if (tr[hi] > res) res = tr[hi]; }
    lo >>= 1; hi >>= 1;
  }
  return res;
}
static void point_max(i64 *tr, int p, i64 v, int base) {
  int i = base + p;
  if (tr[i] >= v) return;
  tr[i] = v;
  i >>= 1;
  while (i) {
    i64 a = tr[2 * i], b = tr[2 * i + 1];
    i64 mx = a > b ? a : b;
    if (tr[i] == mx) break;
    tr[i] = mx;
    i >>= 1;
  }
}

static void solve_chain(int n, const u32 *ea, const u32 *ec) {
  for (int i = 0; i < n - 1; i++) cw_[ea[i]] = ec[i];
  dis2_[1] = 0;
  for (int v = 2; v <= n; v++) dis2_[v] = dis2_[v - 1] + (i64)cw_[v - 1];
  int m = ni();
  int cnt = 0;
  for (int i = 0; i < m; i++) {
    int x,y;ni_pair(x,y);
    i64 v = nll();
    if (x == y) continue;                 // covers no edge -> can never share one
    if (x > y) { int t = x; x = y; y = t; }
    ox[cnt] = (u32)x; oy[cnt] = (u32)y;
    ow[cnt] = (dis2_[y] - dis2_[x]) - v;
    cnt++;
  }
  if (cnt < 2) { pc('F'); pc('\n'); return; }
  int base = 1;
  while (base <= n) base <<= 1;
  for (int i = 0; i < 2 * base; i++) trC[i] = NINF;
  bnN = n + 1;
  for (int i = 1; i <= bnN; i++) bitN[i] = NINF;
  for (int i = 0; i <= n + 1; i++) cstart[i] = 0;
  for (int i = 0; i < cnt; i++) cstart[ox[i]]++;
  { u32 s = 0;
    for (int i = 0; i <= n + 1; i++) { u32 c = cstart[i]; cstart[i] = s; s += c; } }
  for (int i = 0; i < cnt; i++) ord2[cstart[ox[i]]++] = (u32)i;
  i64 best = NINF;
  for (int k = 0; k < cnt; k++) {
    int qi = (int)ord2[k];
    int xq = (int)ox[qi], yq = (int)oy[qi];
    i64 wq = ow[qi];
    { i64 a = range_max(trC, xq + 1, yq, base);
      if (a > NINF / 2) { i64 t = a + wq + dis2_[xq]; if (t > best) best = t; } }
    { i64 b = asuf_qry(yq);
      if (b > NINF / 2) { i64 t = b - (dis2_[yq] - dis2_[xq] - wq); if (t > best) best = t; } }
    point_max(trC, yq, wq - dis2_[yq], base);
    asuf_upd(yq, wq);
  }
  if (best <= NINF / 2) { pc('F'); } else pll(best);
  pc('\n');
}

/* ==== S2 fast path (ported from work/n18y_s2patch.py, adapted by b18e_) ==== */
static u32 s2_ins(u32 o, int pt, i64 deep2) {
  i64 f2 = itm2[pt].f2, g2 = itm2[pt].w;   /* [E18V-G2] g2 == w */
  if (!o) {
    o = ++pool_n;
    pool[o].e = (u32)pt; pool[o].f = (u32)pt; pool[o].mf = f2; pool[o].mg = g2;
    item_lv[pool[o].e] = singval(pt);
    return o;
  }
  if (f2 > pool[o].mf) pool[o].mf = f2;
  if (g2 > pool[o].mg) pool[o].mg = g2;
  u32 x = pool[o].e, y = pool[o].f;
  if (!x) { pool[o].e = pool[o].f = (u32)pt; item_lv[pool[o].e] = singval(pt); return o; }
  i64 v1 = calc(pt, (int)x), v2 = (x == y) ? v1 : calc(pt, (int)y);
  i64 v = v1 > v2 ? v1 : v2;
  { i64 z = v - deep2; if (z > ans) ans = z; }
  i64 v0 = item_lv[pool[o].e];
  if (v0 >= v1 && v0 >= v2) return o;
  if (v1 >= v2) pool[o].f = (u32)pt; else pool[o].e = (u32)pt;
  item_lv[pool[o].e] = v;
  return o;
}
static u32 s2_merge(u32 a, u32 b, i64 deep2) {
  if (!a) return b;
  if (!b) return a;
  leaf_combine(a, b, deep2);
  return a;
}
static void solve_group() {
  int n = ni();
  static u32 deg[MAXN + 2];
  for (int i = 1; i <= n; i++) deg[i] = 0;
  static u32 ea[MAXN], eb[MAXN], ec[MAXN];
  g_chain = 1;
  g_c0 = 1;
  for (int i = 0; i < n - 1; i++) {
    int a,b;ni_pair(a,b);int c=ni();
    if (b != a + 1) g_chain = 0;
    if (c) g_c0 = 0;
    ea[i] = a; eb[i] = b; ec[i] = c;
    deg[a]++; deg[b]++;
  }
  if (g_chain) { solve_chain(n, ea, ec); return; }
  {
    u32 s = 0;
    for (int i = 1; i <= n; i++) { head_[i] = s; s += deg[i]; }
    head_[n + 1] = s;
  }
  {
    static u32 pos[MAXN + 2];
    for (int i = 1; i <= n; i++) pos[i] = head_[i];
    for (int i = 0; i < n - 1; i++) {
      u32 a = ea[i], b = eb[i], c = ec[i];
      eto[pos[a]] = b; ew[pos[a]++] = c;
      eto[pos[b]] = a; ew[pos[b]++] = c;
    }
  }
  {
    int top = 0;
    static u32 stk[MAXN], ptr[MAXN];
    par_[1] = 0; dep_[1] = 0; dis_[1] = 0;
    stk[0] = 1; ptr[1] = head_[1];
    int ec_ = 0, pc_ = 0;
    euler[ec_] = 1; first_[1] = ec_; ec_++;
    pre_[pc_++] = 1;
    while (top >= 0) {
      u32 u = stk[top];
      if (ptr[u] < head_[u + 1]) {
        u32 idx = ptr[u]++;
        u32 v = eto[idx];
        if (v == par_[u]) continue;
        par_[v] = u; dep_[v] = dep_[u] + 1; dis_[v] = dis_[u] + ew[idx];
        first_[v] = ec_; euler[ec_] = v; ec_++;
        if (pc_ < n) pre_[pc_++] = v;
        stk[++top] = v; ptr[v] = head_[v];
      } else {
        top--;
        if (top >= 0) { euler[ec_] = stk[top]; ec_++; }
      }
    }
  }
  {
    int m_ = 2 * n - 1;
    if (!g_chain) {
      int nb=(m_+RMQB-1)/RMQB;
      for (int b=0;b<nb;b++) {
        int l=b*RMQB, r=l+RMQB; if(r>m_)r=m_;
        u32 z=0;
        for (int i=l;i<r;i++) { u32 p=rmq_pack(euler[i]); z=(i==l)?p:rmq_pick(z,p); rmq_pref[i]=z; }
        for (int i=r-1;i>=l;i--) { u32 p=rmq_pack(euler[i]); z=(i==r-1)?p:rmq_pick(p,z); rmq_suf[i]=z; }
        rmq_st[0][b]=rmq_pref[r-1];
      }
      for (int k=1;(1<<k)<=nb && k<RMQLVL;k++)
        for (int b=0;b+(1<<k)<=nb;b++)
          rmq_st[k][b]=rmq_pick(rmq_st[k-1][b],rmq_st[k-1][b+(1<<(k-1))]);
      { /* layers 2+3 over block minima (block min is the block's last position pref) */
        int nsb=(nb+RMQS-1)/RMQS;
        for (int sb=0;sb<nb;sb+=RMQS) {
          int e=sb+RMQS; if(e>nb)e=nb;
          u32 z;
          { int t0=(sb+1)*RMQB; if(t0>m_)t0=m_;
            z=rmq_pref[t0-1]; bpref[sb]=z; }
          for (int b=sb+1;b<e;b++) {
            int t=(b+1)*RMQB; if(t>m_)t=m_;
            z=rmq_pick(z,rmq_pref[t-1]); bpref[b]=z;
          }
          int t2=(e)*RMQB; if(t2>m_)t2=m_;
          z=rmq_pref[t2-1]; bsuf[e-1]=z;
          for (int b=e-2;b>=sb;b--) {
            int t=(b+1)*RMQB; if(t>m_)t=m_;
            z=rmq_pick(rmq_pref[t-1],z); bsuf[b]=z;
          }
          bsp[0][sb/RMQS]=bpref[e-1];
        }
        for (int k=1;(1<<k)<=nsb;k++)
          for (int b=0;b+(1<<k)<=nsb;b++)
            bsp[k][b]=rmq_pick(bsp[k-1][b],bsp[k-1][b+(1<<(k-1))]);
      }
    }
  }
  int m = ni();
  u32 maxdep = 0;
  for (int v = 1; v <= n; v++) if (dep_[v] > maxdep) maxdep = dep_[v];
  static u32 tat[MAXIT];   /* pkey/ppt are written directly at the source: the
                              previous tkey/tpt arrays existed only to be copied
                              into pkey/ppt by the reverse linked-list pass. */
  int nit = 0;
  for (int i = 0; i < m; i++) {
    int x,y;ni_pair(x,y);
    i64 cost = nll();
    int anc = lca_of(x, y);
    i64 len = dis_[x] + dis_[y] - 2 * dis_[anc];
    i64 f2 = 2 * (len - cost);
    i64 g2 = f2 + 2 * dis_[anc];
    i64 base = len - 2 * cost;
    if (x != anc) {
      int id = 2 * i + 1;
      itm[id].v = (u32)y; itm[id].fv = first_[y];
      itm[id].w = base + dis_[x] + dis_[y];
      itm[id].f2 = f2;   /* [E18V-G2] g2 dropped: g2 == w */
      pkey[nit] = dep_[anc] + 1; tat[nit] = x; ppt[nit] = id;
      nit++;
    }
    if (y != anc) {
      int id = 2 * i + 2;
      itm[id].v = (u32)x; itm[id].fv = first_[x];
      itm[id].w = base + dis_[x] + dis_[y];
      itm[id].f2 = f2;   /* [E18V-G2] g2 dropped: g2 == w */
      pkey[nit] = dep_[anc] + 1; tat[nit] = y; ppt[nit] = id;
      nit++;
    }
  }
  // Stable counting scatter: the old reverse linked-list build visited each
  // vertex's entries in ascending e order, exactly as this contiguous layout.
  for (int i = 0; i < n; i++) ord_[i] = pre_[n - 1 - i];
  for (int i = 0; i < n; i++) ordpos_[ord_[i]] = (u32)i;
  /* [E18V-SEQ] group by traversal position, and lay the item payload down at the
     entry's own index so the item id is the entry index.  Stable, so the per-vertex
     insert order is unchanged. */
  for (int v = 0; v <= n + 1; v++) phead2[v] = 0;
  for (int e = 0; e < nit; e++) ++phead2[ordpos_[tat[e]]];
  u32 off = 0;
  for (int v = 0; v < n; v++) {
    u32 count = phead2[v]; phead2[v] = off; off += count;
  }
  phead2[n] = off;
  static u32 write_pos2[MAXN + 2];
  for (int v = 0; v < n; v++) write_pos2[v] = phead2[v];
  for (int e = 0; e < nit; e++) {
    u32 j = write_pos2[ordpos_[tat[e]]]++;
    pkey2[j] = (unsigned short)pkey[e];
    itm2[j + 1] = itm[ppt[e]];   /* id = entry index + 1: 0 stays the pool's empty marker */
  }
  static u32 rt[MAXN];
  for (int v = 1; v <= n; v++) rt[v] = 0;
  pool_n = 0;
  int S = (int)maxdep + 1; if (S < 1) S = 1;
  g_key1 = 1;
  for (int e = 0; e < nit; e++) if (pkey[e] != 1) { g_key1 = 0; break; }
  ans = NINF;
  if (g_key1) {                     /* ==== S2: one-key domain, single-leaf tree ==== */
    for (int oi = 0; oi < n; oi++) {
      u32 t = ord_[oi];
    if (oi + 2 < n) {
      u32 t1 = ord_[oi + 1], t2 = ord_[oi + 2];
      __builtin_prefetch((const void *)&rt[t1], 1, 0);
      __builtin_prefetch((const void *)&rt[t2], 1, 0);
    }
      i64 deep2 = 2 * dis_[t];
      for (u32 c = head_[t]; c < head_[t + 1]; c++) {
        u32 v = eto[c];
        if (v == par_[t]) continue;
        if (!rt[v]) continue;
        rt[t] = s2_merge(rt[t], rt[v], deep2);
      }
      u32 item_end = phead2[oi + 1];
      for (u32 e = phead2[oi]; e < item_end; ++e) {
        if (e + 1 < item_end)
          __builtin_prefetch((const void *)&itm2[e + 1], 0, 0);
        if (e + 2 < item_end)
          __builtin_prefetch((const void *)&itm2[e + 2], 0, 0);
        rt[t] = s2_ins(rt[t], (int)(e + 1), deep2);
      }
      if (rt[t] && (int)dep_[t] <= 1) rt[t] = 0;   /* wipe: keys >= K, only key == 1 exists */
    }
  } else {
  /* [PFSC-rt] rt[] is a random RMW (`rt[t] = ...`, reads of rt[v]) whose index comes from the
     SEQUENTIAL array ord_[], so the address needs no second-level dependency and can be issued
     D iterations early (BRIEF 2.19.325 [PFSC-d]: settlement-type RMW target; 2.19.324: the
     switch is "is the phase's LFB idle").  Pure hint -- no semantics, no state. */
  for (int oi = 0; oi < n; oi++) {
    u32 t = ord_[oi];
    if (oi + 2 < n) {
      u32 t1 = ord_[oi + 1], t2 = ord_[oi + 2];
      __builtin_prefetch((const void *)&rt[t1], 1, 0);
      __builtin_prefetch((const void *)&rt[t2], 1, 0);
    }
    i64 deep2 = 2 * dis_[t];
    for (u32 c = head_[t]; c < head_[t + 1]; c++) {
      u32 v = eto[c];
      if (v == par_[t]) continue;
      if (!rt[v]) continue;
      if (!rt[t]) rt[t] = rt[v];
      else rt[t] = merge_tr(rt[t], rt[v], 1, S, deep2);
    }
    u32 item_end = phead2[oi + 1];
    for (u32 e = phead2[oi]; e < item_end; ++e) {
      if (e + 1 < item_end)
        __builtin_prefetch((const void *)&itm2[e + 1], 0, 0);
      if (e + 2 < item_end)
        __builtin_prefetch((const void *)&itm2[e + 2], 0, 0);
      rt[t] = ins(rt[t], 1, S, (int)pkey2[e], (int)(e + 1), deep2);
    }
    if (rt[t]) rt[t] = wipe(rt[t], 1, S, (int)dep_[t]);
  }
  }
  if (ans <= NINF / 2) { pc('F'); }
  else pll(ans >> 1);
  pc('\n');
}

static void main_solve() {
  int T = ni();
  while (T--) solve_group();
}

#ifdef LOCAL_TEST
int main() {
  size_t sn = fread(g_in, 1, sizeof(g_in), stdin);
  ip_ = (const unsigned char *)g_in; ie_ = ip_ + sn;
  op_ = g_out;
  main_solve();
  fwrite(g_out, 1, (size_t)(op_ - g_out), stdout);
  return 0;
}
#else
int main() { return 0; }
extern "C" void __libc_start_main(void *mm, int argc, char **argv) {
  (void)mm;
  unsigned long *p = (unsigned long *)(argv + argc + 1);
  while (*p) p++;
  p++;
  for (; p[0]; p += 2) if (p[0] == 0x6b637564UL) { D = (DI *)p[1]; break; }
  if (D) {
    ip_ = (const unsigned char *)D->s; ie_ = ip_ + D->sn; op_ = D->o;
    main_solve();
    D->os = (u64)(op_ - D->o);
  }
  __asm__ volatile("syscall" ::"a"(60), "D"(0) : "rcx", "r11", "memory");
  for (;;);
}
#endif

评测结果