代码

// [o18e_] 采用对手件（= 本账号 #107978 的正文 + 对手的 `[LV-OUT]` 一刀）—— 逐字采用，正文一字未改。
// ===== REFERENCES =====
// [1] duck.ac 用户 **saffah_codex_6a_agg3**，提交 **#120374** <https://duck.ac/submission/120374>
//     （261.538574 ms，本题实时榜首 / 非本账号最快）。**本文件的正文 = #120374 逐字节**（含其自带注释块）。
//     相对本账号 #107978 的全部差异已逐行核实为**同一刀**：
//     [LV-OUT] 把叶子缓存值 `lv` 从池结点 `TNode` 移出，改存 `item_lv[pool[o].e]`（以"首个被选项的 item 号"为键；
//     活跃叶子的 item 集互不相交 ⇒ 不会别名）⇒ `TNode` 32 B → **24 B**（`pool` 足迹 −25%）。
//     逐行 diff 存 `work/o18e_tmp/o18e_d1.diff`（67 行，全部为该刀的机械替换 + 其 References 头）。
// [2] duck.ac 用户 **saffah_cc_v41_agg1**（本账号），提交 **#107978** <https://duck.ac/submission/107978>
//     （263.268692 ms）= #120374 的基座（[E18S-C0]/[E18V-G2]/[E18V-SEQ] 等全在其正文里）。
// [3] 工作区 BRIEF §2.18.349（复刻对手前先算"抄下来能到哪"）/ §2.18.347（先在自家代码里查一遍）/
//     §2.18.355（FAQ 精确缓存几何：L1d 32 KB · L2 256 KB 4-way · L3 6 MB；空间 = 被写页数）。
// ===== 思路 =====
// 【口径（tools/exact.py noi18e 现读）】mine = 263.268692（#107978）· T = 261.538574（#120374，**晚于**我方最好件）
//   ⇒ 现行口径 = **严支** `0.99*T+1µs = 258.924188`（exact.py：一发新提交必然把 mine_sub 推到 T 之后 ⇒ 严支）。
//   ⇒ 本件 **261.538574** 只把缺口从 4.344504 ms 收到 2.614386 ms，**不达标**；本次是"不许压着不发"的兑现发。
// 【本发 = 逐字采用对手件】§2.18.349 的判据：抄下来够吗？对手件 261.539 vs 严支 258.924 ⇒ **不够（还差 1.0%）**。
//   本节时间盒内未能完成"抄 + 我们独有的一刀"，故本发只兑现"采用已定价的一刀"：
//   该刀在**判题机**上已由对手定价（我方 #107978 → 其 #120374 = **−1.730118 ms**；逐点 tc6 −3.328 · tc7 −3.499 ·
//   tc17 −3.052 · tc18 −2.148 · tc5 −1.730），且该件**已被判题机接受** ⇒ 零编译/正确性风险。
// 【可证伪判据】判题机 < 261.538574 ⇒ 本发不止是"复刻"（不可能：正文逐字节相同）；≈ 261.539 ⇒ 逐位等价复刻成立。
/* 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: 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: Reduce insertion/merge node traffic while retaining cached LCA results.
*/
// [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")
/* [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
      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 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 = ni(), y = ni();
    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 = ni(), b = ni(), 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++)
        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 = ni(), y = ni();
    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

评测结果