题目理解

我们有一个 $N$ 个城镇的有向无环图 (DAG)，所有边从编号小的城镇指向编号大的城镇。每个城镇有一个河狸朋友。对于 $Q$ 个查询，每个查询给出聚会地点 $T_j$ 和 $Y_j$ 个无法参加的河狸所在城镇，我们需要找出能参加聚会的河狸中，从各自城镇到 $T_j$ 的最长路径的长度。

问题分析

1. 图的性质

• 城镇编号 $1$ 到 $N$ 按海拔从高到低排列
• 所有边从编号小的城镇指向编号大的城镇
• 图是一个 DAG（有向无环图）

2. 查询特点

• 每个查询会禁止 $Y_j$ 个城镇的河狸参加
• 需要快速找出剩余城镇到 $T_j$ 的最长路径
• 总禁止城镇数 $\sum Y_j \leq 10^5$

算法思路

1. 分治策略

代码采用基于数据规模的分治策略：

• 当 $Y_j < B$（$B=100$）时：使用预处理的前 $B$ 长路径信息
• 当 $Y_j \geq B$ 时：动态规划计算最长路径

2. 预处理阶段

对于每个节点，预处理从其出发到其他节点的前 $B$ 长路径：

for (int i = 1; i <= n; i++) {
    if (vec[i].size() < B) {
        vec[i].push_back({0, i});  // 自身路径长度为0
    }
    for (int j : v[i]) {
        merge(i, j);  // 合并路径信息
    }
}

3. 路径合并算法

merge(i, j) 函数将节点 $i$ 的路径信息合并到节点 $j$：

void merge(int x, int y) {
    now.clear();
    int top1 = 0, top2 = 0;
    
    // 归并排序合并路径，保留前B长的不同终点路径
    while (top1 < (int)vec[x].size() && top2 < (int)vec[y].size() && now.size() < B) {
        if (vec[x][top1].first + 1 > vec[y][top2].first) {
            // 选择从x延伸的路径
            if (!flag[vec[x][top1].second]) {
                flag[vec[x][top1].second] = true;
                use.push_back(vec[x][top1].second);
                now.push_back({vec[x][top1].first + 1, vec[x][top1].second});
            }
            top1++;
        } else {
            // 选择y原有的路径
            if (!flag[vec[y][top2].second]) {
                flag[vec[y][top2].second] = true;
                use.push_back(vec[y][top2].second);
                now.push_back(vec[y][top2]);
            }
            top2++;
        }
    }
    // ... 处理剩余路径
}

4. 查询处理

情况1：禁止城镇数少 ($Y_j < B$)

int maxx = -1;
for (pair<int, int> i : vec[t]) {
    if (s.find(i.second) == s.end()) {  // 城镇未被禁止
        maxx = max(maxx, i.first);
    }
}
cout << maxx << endl;

情况2：禁止城镇数多 ($Y_j \geq B$)

// 动态规划计算最长路径
for (int i = 1; i <= n; i++) f[i] = 0;
for (int i : s) f[i] = -INF;  // 禁止的城镇设为负无穷

for (int i = 1; i <= n; i++) {
    for (int j : v[i]) {
        f[j] = max(f[j], f[i] + 1);
    }
}

关键算法细节

1. 路径信息存储

vec[i] 存储从节点 $i$ 出发的前 $B$ 长路径，每个元素为 {路径长度, 终点城镇}

2. 归并合并策略

• 使用类似归并排序的方法合并路径列表
• 保持路径按长度降序排列
• 使用标记数组避免重复终点

3. 复杂度平衡

• 预处理：$O((N+M) \times B)$，其中 $B=100$
• 小禁止集查询：$O(B)$
• 大禁止集查询：$O(N+M)$

由于 $\sum Y_j \leq 10^5$，大禁止集查询的总复杂度可控。

算法优化

1. 空间优化

只存储前 $B$ 长路径，将空间从 $O(N^2)$ 降到 $O(N \times B)$

2. 时间优化

• 利用 DAG 性质按拓扑序处理
• 根据禁止集大小选择不同算法

3. 实现技巧

• 使用标记数组和临时容器避免重复计算
• 利用 vector::swap 高效更新路径列表

复杂度分析

• 预处理阶段：$O((N+M) \times B \log B)$
• 查询阶段：
  • 小禁止集：$O(Q_{small} \times B)$
  • 大禁止集：$O(Q_{large} \times (N+M))$
• 总复杂度：在数据范围内可接受

算法标签

• 动态规划：大禁止集情况下的路径计算
• 贪心算法：选择前 $B$ 长路径
• 分治思想：根据数据规模选择不同算法
• 图论：DAG 上的最长路径问题
• 预处理：预先计算关键路径信息

总结

这道题通过巧妙的分治策略和预处理技术解决了大规模 DAG 上的带限制最长路径查询问题：

1. 问题分析：识别图的 DAG 性质和查询特点
2. 算法设计：根据禁止集大小采用不同策略
3. 预处理优化：存储前 $B$ 长路径信息支持快速查询
4. 实现技巧：高效的路径合并和查询处理

该解法充分利用了问题的特殊约束条件，通过平衡预处理和查询开销，实现了高效的问题求解。