题解

问题分析

这是一个基环树 + 线段树合并的复杂问题。邮局系统构成一个有向图，每个邮局 $i$ 指向 $P_i$，形成基环树结构。包裹需要从起点 $A_j$ 运输到终点 $B_j$，求所有包裹到达目的地的最早可能时间。

关键观察

1. 图结构：邮局网络形成基环树（功能森林）
2. 可达性：包裹只能沿着有向边运输，必须检查 $A_j$ 是否能到达 $B_j$
3. 时间计算：运输时间取决于路径长度和资源竞争

算法思路

基环树分解 + 线段树合并优化：

基环树处理

1. 识别环：使用拓扑排序找出所有环
2. 复制节点：为环上节点创建副本，处理环上的特殊路径
3. 树链处理：对每棵树进行DFS，计算DFS序和子树大小

线段树合并

• 使用动态开点线段树维护每个节点的包裹信息
• 线段树存储深度信息，用于计算运输时间
• 通过合并子树线段树来聚合信息

核心数据结构

并查集检查连通性

struct DSU {
    int fa[N];
    int find(int x) {
        if(fa[x] == x) return x;
        return fa[x] = find(fa[x]);
    }
    void merge(int x, int y) {
        fa[find(x)] = find(y);
    }
} T;

动态开点线段树

struct SegTree {
    struct Node {
        int val, cnt;  // 最大值和计数
        int ls, rs;    // 左右儿子
    } t[N << 5];
    // 支持合并和更新操作
    void merge(int &x, int a, int b, int l, int r);
    void update(int &x, int l, int r, int pos, int v);
};

算法步骤

1. 输入处理：读入邮局网络和包裹信息
2. 环检测：用拓扑排序找出基环树的所有环
3. 节点复制：为环上节点创建副本，处理环上路径
4. DFS预处理：计算DFS序、深度、子树大小
5. 可达性检查：对每个包裹检查 $A_j$ 是否能到达 $B_j$
6. 线段树操作：
   • 在起点添加包裹
   • 在终点删除包裹
   • 合并子树信息
7. 答案计算：通过线段树的最大值计算最早完成时间

关键函数

包裹添加

void add(int a, int b) {
    upd[a]++;  // 在起点a添加包裹
    del[b].push_back(dep[a]);  // 在终点b记录要删除的深度
}

线段树合并求答案

void dfs2(int x) {
    for(int to : G[x]) {
        dfs2(to);
        S.merge(S.rt[x], S.rt[x], S.rt[to], 1, 2*n);
    }
    S.update(S.rt[x], 1, 2*n, dep[x], upd[x]);
    for(int i : del[x])
        S.update(S.rt[x], 1, 2*n, i, -1);
    ans = max(ans, S.t[S.rt[x]].val - dep[x]);
}

复杂度分析

• 环检测：$O(N)$
• DFS预处理：$O(N)$
• 线段树操作：$O((N+M)\log N)$
• 总复杂度：$O((N+M)\log N)$

特殊情况处理

1. 不可达情况：如果 $A_j$ 无法到达 $B_j$，直接输出 -1
2. 环上运输：通过节点副本处理环上的特殊路径
3. 资源竞争：同一时刻一个邮局只能发送一个包裹

算法标签

• 基环树
• 线段树合并
• 动态开点线段树
• 拓扑排序
• DFS序
• 图论
• 资源调度