题目大意

给定一棵包含 $N$ 个城市的树，Fabijan 需要按顺序访问城市 $1, 2, \ldots, N$。每条边有两种通行方式：

• 单次票：每次通过花费 $C_{i1}$ 欧元
• 多次票：一次性花费 $C_{i2}$ 欧元，可无限次使用

求完成整个旅程的最小总花费。

问题分析

关键观察

1. 树结构：城市间构成一棵树，任意两点间有唯一简单路径
2. 访问顺序：需要依次访问 $1 \to 2 \to 3 \to \cdots \to N$，共 $N-1$ 段行程
3. 票务决策：对于每条边，如果经过次数 $\times C_{i1} \leq C_{i2}$，则选择单次票，否则选择多次票

问题转化

核心问题转化为：

1. 计算每条边在所有 $N-1$ 段行程中被经过的总次数
2. 根据经过次数为每条边选择最优票务方案

算法设计

方法一：LCA + 树上差分

核心思想：利用最近公共祖先和树上差分高效统计边经过次数。

步骤

1. 预处理：

   • 构建树的邻接表表示
   • 预处理LCA（倍增法或Tarjan算法）
   • 记录每个节点的深度和父节点信息

2. 路径统计：

   • 对于每段行程 $i \to i+1$，计算路径 $LCA(i, i+1)$
   • 路径可分解为：$i \to LCA(i, i+1) \to i+1$
   • 使用树上差分标记路径上的边

3. 差分统计：

   • 从叶子节点向根节点进行DFS
   • 累加差分数组，得到每条边的实际经过次数

4. 成本计算：

   • 对于每条边 $e$，经过次数为 $cnt_e$
   • 成本 = $\min(cnt_e \times C_{e1}, C_{e2})$
   • 累加所有边的成本得到总花费

复杂度分析

• LCA预处理：$O(N \log N)$
• 路径处理：$O(N \log N)$
• 差分统计：$O(N)$
• 总复杂度：$O(N \log N)$

方法二：欧拉序 + 树状数组

核心思想：利用欧拉遍历序和树状数组统计边经过次数。

步骤

1. 欧拉序预处理：

   • 对树进行DFS，记录每个节点的入序和出序
   • 建立欧拉序列

2. 路径标记：

   • 对于路径 $u \to v$，在欧拉序上进行区间标记
   • 使用树状数组维护标记信息

3. 次数统计：

   • 通过树状数组查询每条边的经过次数
   • 同样使用贪心策略选择票务方案

方法三：重链剖分

核心思想：使用树链剖分高效处理路径操作。

步骤

1. 树链剖分预处理：

   • 进行重链剖分，建立线段树结构
   • 记录每个节点所在重链信息

2. 路径操作：

   • 对于每段行程 $i \to i+1$，在剖分后的链上进行区间加操作
   • 使用线段树维护边经过次数

3. 结果统计：

   • 查询每条边的最终经过次数
   • 计算最小总成本

实现细节

LCA实现（倍增法）

// 伪代码
void dfs(int u, int parent) {
    depth[u] = depth[parent] + 1;
    fa[u][0] = parent;
    for (int i = 1; i <= LOG; i++) {
        fa[u][i] = fa[fa[u][i-1]][i-1];
    }
    for (auto &edge : adj[u]) {
        if (edge.v != parent) {
            dfs(edge.v, u);
        }
    }
}

int lca(int u, int v) {
    if (depth[u] < depth[v]) swap(u, v);
    for (int i = LOG; i >= 0; i--) {
        if (depth[fa[u][i]] >= depth[v]) {
            u = fa[u][i];
        }
    }
    if (u == v) return u;
    for (int i = LOG; i >= 0; i--) {
        if (fa[u][i] != fa[v][i]) {
            u = fa[u][i];
            v = fa[v][i];
        }
    }
    return fa[u][0];
}

树上差分实现

// 伪代码
void mark_path(int u, int v) {
    int p = lca(u, v);
    diff[u]++;
    diff[v]++;
    diff[p] -= 2;
}

void dfs_count(int u, int parent) {
    for (auto &edge : adj[u]) {
        if (edge.v != parent) {
            dfs_count(edge.v, u);
            edge_count[edge.id] = diff[edge.v];
            diff[u] += diff[edge.v];
        }
    }
}

关键洞察

算法选择

• 推荐方法一：LCA + 树上差分，实现相对简单，效率高
• 适用于 $N \leq 2 \times 10^5$ 的大规模数据

优化技巧

1. 空间优化：使用邻接表存储树结构
2. 时间优化：预处理LCA避免重复计算
3. 常数优化：使用数组代替STL容器

边界情况

1. 单次票更优：当 $C_{i2} \geq cnt \times C_{i1}$ 时选择单次票
2. 多次票更优：当 $C_{i2} < cnt \times C_{i1}$ 时选择多次票
3. 相等情况：根据题意 $C_{i1} \leq C_{i2}$，相等时选择单次票

复杂度对比

总结

本题的核心在于将复杂的旅程规划问题转化为树上的路径统计问题。通过LCA快速计算路径，利用树上差分高效统计边经过次数，最后使用贪心策略为每条边选择最优票务方案。这种"树结构 + LCA + 差分 + 贪心"的组合是解决此类问题的经典模式。

关键点：理解树上差分的原理，掌握LCA算法的实现，以及正确应用贪心决策策略。