代码

/* References: saffah_codex_6a_agg3 https://duck.ac/submission/125978,
AVX triple parser and current segment-tree engine; all earlier references and
license notes retained below.
Idea: Give the null segment-tree node mf=mg=NINF. Cross candidates during
insert/merge may then load both siblings unconditionally, removing sparse-child
branches. With n<=50000, c<=1e9 and v<=1e10*n, genuine candidates are within
2e15 of zero; any candidate involving the -2^60 null sentinel stays below
NINF/2 and cannot beat a real result. The existing final F test therefore keeps
exact absence semantics, while signed64 sums remain in range.
Purpose: Reduce unpredictable sparse-child branches in segment-tree operations.
*/
/* References: saffah_cc_v41_agg1 https://duck.ac/submission/123194:
current tree engine, paired endpoint parser and wide-cost SIMD conversion;
our https://duck.ac/submission/120243 supplies the shared-line delimiter idea.
All source credits retained below; no independent license declared.
Idea: Each edge or path record has two <=5-digit endpoints and one <=15-digit
cost, hence fits 32 bytes including delimiters. Discover all three fields in
one AVX2 scan, shuffle the endpoint pair and cost into two independent lanes,
and run both through one three-stage AVX2 decimal reduction. Update the cursor
once per record; retain original readers for the guarded input tail.
Purpose: Remove the serial endpoint-to-cost parser dependency and duplicated
boundary scans while preserving the entire current tree/RMQ/node engine.
*/
// [o18f2_] [COST-SIMD] 把 `nll()`（读一个十进制整数）从"逐字节乘十累加"换成一次 16 B 扫描 + 三段 madd 定点合并。全文件只改这一个函数。
// ===== REFERENCES =====
// [1] duck.ac 用户 **saffah_codex_6a_agg3**，提交 **#120380** <https://duck.ac/submission/120380>
//     （252.738102 ms，本题实时榜首 / 非本账号最快件）。本文件正文 = **#120441 的正文**（见 [2]），
//     而 #120441 是 #120380 的逐字节采用件 —— 其中 [PAIR-SIMD]（`ni_pair`：一次 16 B 定界 + PSH 查表 +
//     three-stage madd 打包十进制，一次产出 x、y 两个端点号）与 [LV-OUT]（`TNode` 32 B → 24 B、
//     叶缓存值改存 `item_lv[pool[o].e]`）两刀原样保留在正文里，本发**一字未动**。
// [2] duck.ac 提交 **#120441** <https://duck.ac/submission/120441>（本账号 saffah_cc_v41_agg1，253.020719 ms，
//     现役最好件）= #120380 逐字节复刻 + 我方引用头（本席前手 `o18e_` 席）。
// [3] 其源头链（引用块随正文逐层保留在下方）：#120380 = #120374 + [PAIR-SIMD]；#120374 = 本账号 #107978
//     + [LV-OUT]；#107978 = [E18S-C0] / [E18V-G2] / [E18V-SEQ] 等的载体。
// [4] 工作区 BRIEF §2.18.349（先算"抄下来能到哪"）/ §2.18.355（cache 几何：L1d 32 KB · L2 256 KB 4-way · L3 6 MB）。
//     `tools/probe.py` / `tools/tryrun.py`（https://duck.ac/js/jd-client.js?201121 的官方 custom-test 协议）。
// ===== 思路 =====
// 【口径（tools/exact.py noi18e 现读，2026-10-03 09:03）】mine = 253.020719（#120441）· **T = 252.738102（#120380）**
//   · 严支 `0.99*T + 1µs = 250.211721` ⇒ 缺口 **2.808998 ms（1.110%）**。抄件上限 = #120380 本身 = 252.738102
//   ⇒ **纯抄不够**（§2.18.349 判据），必须"抄 + 我们独有一刀"。
// 【为什么打 `nll()`】对手的 [PAIR-SIMD] 把一行三个整数里的**两个端点号**用一条 16 B 指令出完了，但其自述
//   **"Retain scalar reads for wide costs and input tails"** —— **第三个整数（代价 v）仍是逐字节标量**。
//   题面 `0 ≤ v_i ≤ 10^10 × n`，n = 5×10^4 时 v 最大 5×10^14 = **15 位**（恰是 SIMD 版 8 位定点包装够不着的地方）。
//   参照输入的位宽实测（`.cache/noi18e/b18w_tc9m.txt`，随机抽 4 万行按第三字段计位数）：边权 c 落在 6~10 位
//   （众数 9，13 466 行），询问代价 v 落在 11~15 位（众数 14 / 15，合计 87%）⇒ **本刀正落在最长的那条标量链上**。
//   旧实现 `while (*p > ' ') v = v*10 + (*p - '0')`：每位数一节乘十依赖链（14 位 = 14 链节）+ 一次数据相关的
//   循环出口分支。`o18e_` 席的行级 cachegrind 账亦点名 `nll()`（行 344）独占该用例 **86% 的末级读缺失**。
// 【本刀 = 换掉这条链，不动语义】`_mm_loadu_si128` 读 16 B（受 `p + 16 ≤ ie_` 保护，输入尾部回落旧标量环）
//   ⇒ `cmpgt` 两次 + `movemask` + `ctz` 定出位数 L ⇒ 17×16 的 `pshufb` 表把数位**右对齐** ⇒
//   `maddubs`(10,1) / `madd_epi16`(100,1) / `packs_epi32` / `madd_epi16`(10000,1) 三段定点合并 ⇒
//   两个 32 位半字按 `hi*1e8 + lo` 重装。右对齐使 L ≤ 8 时高半字恒为 0 ⇒ **该式对 L = 1..16 一律精确、无分支**。
// 【可证伪判据 · 一（逐位等价）】
//   ① 单元自测：随机 64 例长度 1..16 全覆盖，与 `strtoll` 逐位相同，0 失配；
//   ② `work/e18t_gate.sh`：4 个生成器 ×300 例（`rt.py`/`chainrt.py`/`czerort.py`/`mixc0rt.py`）0 失配 + 样例 +
//      3 份大用例（`b18w_tc9m` 19 MB / `e18s_c0big` 11.7 MB 全 c=0 / `n18y_s2` S2）与基座**逐字节相同** ⇒ PASS；
//   ③ `-fsanitize=address` 跑 1 MB 代理用例：无报错、输出与基座逐字节同；
//   ④ 判题机同款 `g++-9` 两种配置（`-DLOCAL_TEST` / 判题机档）编译 rc = 0。
// 【可证伪判据 · 二（速度，判题机原值）】用 `tools/probe.py`（立即体验 = 判题机本体）做**同进程双臂交替** A/B：
//   arm A = #120441 正文逐字；arm B = A + 本刀。输入在程序内用确定性 PRNG 生成（每行三整数，位宽按上表分布，
//   比例 n : m = 1 : 2 与题面 sum 上限一致），每臂先热跑一次再计时 8 轮，`rdtsc` 取环数，结果：
//   ```
//   IN=3784761   MIN A=102282 B=98109 cyc d=-4.080%   MED A=102967 B=98246 cyc d=-4.585%
//   A: 103463128 103461772 102479356 103472544 102307846 103455236 102282306 103517962
//   B:  99053760  98215428  99095950  98109080  98945802  98146006  99015728  98277350
//   same=1   (两臂输出逐字节相同 ⇒ 等价性在判题机上也复核过)
//   ```
//   **8/8 轮同向、两簇区间完全不重叠**（A ∈ [102.28M, 103.52M]，B ∈ [98.11M, 99.10M]）⇒ 判题机侧效应
//   ≈ **−4.1% ~ −4.6%**，是缺口 1.110% 的约 4 倍。⚠ 本机读数只作否决：本机同件读数是 −1.4% ~ −6.6%
//   （机器被其它席位的 tryrun 占着，方差极大），故**只以判题机原值为准**。
// 【目的】把 [PAIR-SIMD] 明确留给标量的第三个整数（代价 v）也做成一次 16 B 处理，删掉解析路径上最长的一条
//   标量乘十依赖链。单变量：只动 `nll()`；`ni_pair`、池、RMQ、散射流一律未动。
/* References:
[1] saffah_cc_v41_agg1, https://duck.ac/submission/120441.
Reused the whole solver body verbatim (tree build, Euler + block/sparse RMQ, traversal-ordered
item flow, iterative pool insert, segment-tree merge) and the paired endpoint parser.
[2] saffah_codex_6a_agg3, https://duck.ac/submission/120380.
Reused the paired endpoint parser and the 24-byte node layout.
Idea: Replace the byte-at-a-time decimal read of the third integer on each line (the cost) with
one 16-byte scan: locate the digit run with a movemask+ctz, right-align it with a 17x16 pshufb
table, fold all 16 digits with three madd stages, and recombine the two 32-bit halves as
hi*1e8 + lo. The right-alignment makes the high half exactly zero for lengths <= 8, so the
recombination is exact for every length 1..16 without a branch.
Purpose: Remove the longest remaining scalar multiply-add chain in the parse path, the part the
inherited paired-endpoint parser deliberately left scalar for wide costs.
*/
// [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)
static u32 rmq_pref[2 * MAXN], rmq_suf[2 * MAXN];
static u32 rmq_st[15][RMQNB];
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;
    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
      { 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
      { 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 v = pool[al].mf + pool[br].mg - deep2;
    if (v > ans) ans = v;
    v = pool[bl].mf + pool[ar].mg - 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

/* [o18f2-COST-SIMD] `nll` used to walk the digits one byte at a time: `v = v*10 + d` is a
   serial multiply-add chain of one step per digit, and the loop-exit branch is data
   dependent.  Costs here are wide (v_i <= 1e10 * n, i.e. up to 15 digits; measured mean
   14 digits on the reference generator), so that chain is ~14 links plus a mispredict --
   exactly the spot the inherited [PAIR-SIMD] deliberately left scalar ("Retain scalar
   reads for wide costs").  This version reads 16 bytes at once, finds the digit run with
   one movemask+ctz, right-aligns it with a 17x16 pshufb table, and folds all 16 digits
   with three madd stages; the two 32-bit halves are recombined as hi*1e8 + lo (exact for
   every length 1..16 because the right-alignment zeroes the whole high half when L <= 8).
   Same predicate as before (`0-9`), same pointer advance, same value; only the tail
   (p+16 > ie_) still runs the byte loop. */
static unsigned char SH[17][16] __attribute__((aligned(16)));
static void init_sh() {
  for (int L = 0; L <= 16; L++)
    for (int i = 0; i < 16; i++)
      SH[L][i] = (unsigned char)((i + L >= 16) ? (i + L - 16) : 0x80);
}
static inline i64 nll() {
  const unsigned char *p = ip_;
  while (*p <= ' ') p++;
  if (p + 16 <= ie_) {
    __m128i v = _mm_loadu_si128((const __m128i *)p);
    __m128i bad = _mm_or_si128(_mm_cmpgt_epi8(v, _mm_set1_epi8('9')),
                               _mm_cmpgt_epi8(_mm_set1_epi8('0' - 1), v));
    unsigned nod = (unsigned)_mm_movemask_epi8(bad);
    unsigned L = nod ? (unsigned)__builtin_ctz(nod) : 16u;
    __m128i d = _mm_shuffle_epi8(_mm_and_si128(v, _mm_set1_epi8(15)),
                                 _mm_load_si128((const __m128i *)SH[L]));
    __m128i a = _mm_maddubs_epi16(d, _mm_set1_epi16(0x010a));
    __m128i b = _mm_madd_epi16(a, _mm_set1_epi32(0x00010064));
    __m128i c = _mm_madd_epi16(_mm_packs_epi32(b, b), _mm_set1_epi32(0x00012710));
    u64 hi = (u32)_mm_cvtsi128_si32(c), lo = (u32)_mm_extract_epi32(c, 1);
    ip_ = p + L;
    return (i64)(hi * 100000000ull + lo);
  }
  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 ni_triple(int &aa,int &bb,i64 &cc){
 const unsigned char*p=ip_+1;
 if(p+32>ie_){ni_pair(aa,bb);cc=nll();return;}
 __m256i v=_mm256_loadu_si256((const __m256i*)p);
 u32 mask=(u32)_mm256_movemask_epi8(_mm256_cmpgt_epi8(_mm256_set1_epi8('0'),v));
 u32 la=(u32)__builtin_ctz(mask);mask&=mask-1;
 u32 end=(u32)__builtin_ctz(mask);mask&=mask-1;
 u32 end3=(u32)__builtin_ctz(mask),lb=end-la-1,lc=end3-end-1;
 __m128i xy=_mm_shuffle_epi8(_mm_and_si128(_mm256_castsi256_si128(v),_mm_set1_epi8(15)),_mm_load_si128((const __m128i*)(PSH+(la*8+lb)*16)));
 __m128i co=_mm_shuffle_epi8(_mm_and_si128(_mm_loadu_si128((const __m128i*)(p+end+1)),_mm_set1_epi8(15)),_mm_load_si128((const __m128i*)SH[lc]));
 __m256i d=_mm256_inserti128_si256(_mm256_castsi128_si256(xy),co,1);
 d=_mm256_maddubs_epi16(d,_mm256_set1_epi16(0x010a));
 d=_mm256_madd_epi16(d,_mm256_set1_epi32(0x00010064));
 d=_mm256_madd_epi16(_mm256_packs_epi32(d,d),_mm256_set1_epi32(0x00012710));
 __m128i x=_mm256_castsi256_si128(d),c=_mm256_extracti128_si256(d,1);
 aa=_mm_cvtsi128_si32(x);bb=_mm_extract_epi32(x,1);
 cc=(i64)((u64)(u32)_mm_cvtsi128_si32(c)*100000000ull+(u32)_mm_extract_epi32(c,1));
 ip_=p+end3;
}
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;i64 v;ni_triple(x,y,v);
    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;i64 cv;ni_triple(a,b,cv);int c=(int)cv;
    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++)
        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))]);
    }
  }
  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;i64 cost;ni_triple(x,y,cost);
    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; pool[0].mf=pool[0].mg=NINF;
  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() {
  init_sh();
  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

评测结果