题解：P14365 [JOISC 2018] 高速公路建设 / Construction of Highway

[JOISC 2018] 高速公路建设 / Construction of Highway 题解

1. 成本计算：每次建设时，需统计从首都（城市 1）到城市 Aj的唯一最短路径上，所有 “前序城市活力值> 后序城市活力值” 的相邻城市对数量。
2. 活力值更新：计算成本后，将上述路径上所有城市的活力值统一更新为 Bj 的活力值。

1. 路径唯一性： 题目明确 “1 到Aj 的最短路径唯一”，结合建设规则（Aj 已连通 1，Bj 未连通），可知每次建设的路径是树的一条 “从根（1）到 Aj 的路径”（本质是构建一棵以 1 为根的生成树）。
2. 更新的幂等性： 若一条路径被多次更新，后续更新会覆盖之前的活力值。因此，路径上的活力值最终会变成最后一次更新时 Bj 的值，且同一路径段的活力值会趋于 “一致”。
3. 逆序对的简化： 当路径上的城市活力值全部相同时，逆序对数量为 0；若路径由多个 “活力值相同的连续段” 组成，则逆序对仅存在于相邻段的交界处（前一段活力值 > 后一段活力值时贡献 1）。

• parent[x]：块的父节点（用于路径压缩）。
• value[x]：块的活力值。cnt[x]：块内城市的数量（仅根节点有效）。
• inv[x]：块内的逆序对数量（仅根节点有效，实际为块内相邻城市对的逆序贡献，因块内活力值相同，inv[x] = 0）。
• above_inv[x]：当前块与其父块之间的逆序贡献（若父块活力值 > 当前块活力值，贡献 1，否则 0）。

1. find 函数： 带路径压缩，找到城市 x 所在块的根节点，并维护路径上的逆序对总数（通过累加 above_inv）。
2. merge 函数： 将两个相邻块合并（当路径更新时，所有块的活力值变为 (B_j)，此时块间逆序贡献消失，可合并为一个大的块）。

1. 初始化： 每个城市初始为独立块，value[x] = C[x]，cnt[x] = 1，inv[x] = 0，above_inv[x] = 0（根节点无父块）。
2. 处理每次建设：
   a. 调用 find(A_j)，获取从Aj 到根（1）的路径上的总逆序对数量（即本次建设的成本），并输出。
   b. 再次遍历路径（通过 find 的路径压缩，路径已扁平化），将路径上所有块的活力值更新为 Bj 的活力值，并合并相邻块（此时块间逆序贡献为 0，可安全合并）。