「KTSC 2024 R1」警察与小偷 题解

问题分析

这是一个在树形结构上的追及问题。警察和小偷在树上的不同节点出发，以不同速度移动，采用最优策略，求警察抓住小偷的最短时间。

关键难点：

• 树形结构上的最优路径选择
• 速度差异导致的策略变化
• 在边上任意位置相遇的可能性

算法思路：树链剖分 + 二分查找

1. 树结构预处理

树链剖分初始化

void dfs1(int u) {
    dep[u] = dep[fa[u]] + 1, siz[u] = 1;
    for (auto [v, w] : to[u]) {
        to[v].erase(find(all(to[v]), make_pair(u, w)));
        fa[v] = u, faw[v] = w;
        d[v] = d[u] + w;  // 到根节点的距离
        dfs1(v);
        siz[u] += siz[v];
        if (siz[v] > siz[son[u]]) son[u] = v;
        f[u] = max(f[u], f[v] + w);  // 子树中最远距离
    }
}

功能：

• 计算深度、子树大小、重儿子
• 预处理到根节点的距离
• 计算每个节点到子树中最远叶子的距离

第二次DFS：树链剖分

void dfs2(int u, int t) {
    top[u] = t;
    pos[dfn[u] = ++dft] = u;
    // 计算次远距离用于后续判断
    ll fi = g[u] + faw[u], se = 0;
    for (auto [v, w] : to[u]) {
        if (f[v] + w > fi) se = fi, fi = f[v] + w;
        else se = max(se, f[v] + w);
    }
    for (auto [v, w] : to[u]) {
        g[v] = f[v] + w == fi ? se : fi;
    }
    if (son[u]) dfs2(son[u], t);
    for (auto [v, w] : to[u])
        if (v ^ son[u]) dfs2(v, v);
}

2. 关键判断函数

根据速度关系分为两种情况：

情况1：警察速度 ≤ 小偷速度 (v1 <= v2)

bool check1(int u, int x, int t, int v, int v1, int v2) {
    ll d1 = d[u] - d[x];  // 警察到x的距离
    ll d2 = d[x] + d[v] - d[t] * 2;  // 小偷到x的距离
    return d1 * v2 > d2 * v1;  // 比较时间
}

bool check3(int u, int t, int x, int v, int v1, int v2) {
    ll d1 = d[u] + d[x] - d[t] * 2;  // 警察到x的距离
    ll d2 = d[v] - d[x];  // 小偷到x的距离
    return d1 * v2 > d2 * v1;
}

情况2：警察速度 > 小偷速度 (v1 > v2)

bool check2(int u, int x, int t, int v, ll w, int v1, int v2) {
    ll d1 = d[u] - d[x] + w;
    ll d2 = d[x] + d[v] - d[t] * 2 + w;
    return d1 * v2 > d2 * v1;
}

bool check4(int u, int t, int x, int v, int v1, int v2) {
    ll d1 = d[u] + d[x] - d[t] * 2 + f[x];  // 考虑最远距离
    ll d2 = d[v] - d[x] + f[x];
    return d1 * v2 > d2 * v1;
}

3. 核心查询算法

frac query(int u, int v, int v1, int v2) {
    int t = LCA(u, v);  // 求最近公共祖先
    
    if (v1 <= v2) {
        // 警察速度较慢，需要拦截策略
        if (u != t && (v == t || check1(u, t, t, v, v1, v2))) {
            // 情况1：在警察路径上拦截
            // 二分查找最优拦截点
            int x = u;
            for (; dep[fa[top[x]]] > dep[t]; x = fa[top[x]]) {
                if (check1(u, fa[top[x]], t, v, v1, v2)) break;
            }
            // 在重链上二分查找精确位置
            int l = dep[t] > dep[fa[top[x]]] ? dfn[t] : dfn[top[x]] - 1;
            int r = dfn[x], mid;
            while (l + 1 < r) {
                mid = (l + r) >> 1;
                if (check1(u, pos[mid], t, v, v1, v2)) l = mid;
                else r = mid;
            }
            x = pos[r];
            return {d[u] - d[fa[x]] + g[x], v1};
        } else {
            // 情况2：在小偷路径上追击
            // 类似地二分查找
            // ...
            return {d[u] + d[x] - d[t] * 2 + f[x], v1};
        }
    } else {
        // 警察速度较快，可以直接追击
        // 类似地分为两种情况处理
        // ...
    }
}

4. 分数处理

struct frac {
    ll x;  // 分子
    int y; // 分母
};

bool operator < (const frac &a, const frac &b) {
    return a.x * b.y < b.x * a.y;  // 交叉相乘比较
}

5. 主函数

vector<array<ll, 2>> police_thief(vector<int>A, vector<int>B, vector<int>D, 
                                 vector<int>P, vector<int>V1, vector<int>T, vector<int>V2) {
    int n = A.size() + 1, m = P.size();
    
    // 建图
    for (int i = 0; i < n - 1; i++) {
        A[i]++, B[i]++;  // 转换为1-index
        to[A[i]].push_back({B[i], D[i]});
        to[B[i]].push_back({A[i], D[i]});
    }
    
    // 预处理
    dfs1(1);
    dfs2(1, 1);
    
    // 处理每个查询
    vector<array<ll, 2>> ans(m);
    for (int i = 0; i < m; i++) {
        int u = P[i] + 1, v = T[i] + 1, v1 = V1[i], v2 = V2[i];
        auto a = query(u, v, v1, v2);
        ans[i][0] = a.x, ans[i][1] = a.y;
    }
    return ans;
}

算法复杂度

• 预处理：$O(N)$ 两次DFS
• 每次查询：$O(\log^2 N)$
  • LCA查询：$O(\log N)$
  • 树链上的二分查找：$O(\log N)$
• 总复杂度：$O(N + Q\log^2 N)$

关键优化

1. 树链剖分：将树分解为重链，支持高效路径操作
2. 二分查找：在路径上快速定位最优相遇点
3. 分类讨论：根据速度关系采用不同策略
4. 分数表示：避免浮点数精度问题

策略分析

警察速度慢时 (v1 <= v2)

• 拦截策略：警察预测小偷路径，提前到达拦截点
• 关键观察：必须在LCA之前拦截，否则无法追上

警察速度快时 (v1 > v2)

• 追击策略：警察可以直接追击，考虑小偷可能逃往远端
• 最远距离：利用预处理的最远距离信息

该解法通过树链剖分和精细的策略分析，高效解决了树上的追及问题。