树上路径子路径查询问题 题解

问题分析

给定一棵 $n$ 个节点的树，有 $P$ 个盘子（路径）和 $Q$ 个水果（路径）。对于每个水果，需要找到所有包含该水果路径的盘子中权值第 $k$ 小的。

形式化地说：对于水果路径 $(u_i, v_i)$，找到所有满足盘子路径 $(a_j, b_j)$ 是 $(u_i, v_i)$ 的子路径的盘子中，权值 $c_j$ 的第 $k_i$ 小值。

关键观察

1. 子路径判定条件

在树上，路径 $A$ 是路径 $B$ 的子路径，当且仅当： $A$ 的两个端点都在 $B$ 上，或者$A$ 完全包含在 $B$ 中

2. 问题转化

将问题转化为：对于每个水果路径，查询所有完全包含在该路径内的盘子路径，求这些盘子权值的第 $k$ 小值。

算法思路

1. 树链剖分与LCA

首先对树进行预处理：

计算每个节点的深度、父节点

进行树链剖分，得到DFS序

预处理LCA（最近公共祖先）

namespace HLD {
    int fa[MX], dep[MX], siz[MX], hs[MX], top[MX], pos[MX];
    std::map<int, int> son[MX];
    
    void DFS(int u) {
        siz[u] = 1;
        for (int v : T[u])
            if (v != fa[u]) {
                fa[v] = u;
                dep[v] = dep[u] + 1;
                DFS(v);
                siz[u] += siz[v];
                if (siz[v] > siz[hs[u]]) hs[u] = v;
            }
    }
    
    void DFS1(int u, int tp) {
        static int tot = 0;
        pos[u] = ++tot;
        top[u] = tp;
        if (hs[u]) {
            DFS1(hs[u], tp);
            son[u].insert({pos[hs[u]], hs[u]});
        }
        for (int v : T[u])
            if (v != fa[u] && v != hs[u]) {
                DFS1(v, v);
                son[u].insert({pos[v], v});
            }
    }
    
    int lca(int u, int v) {
        while (top[u] != top[v]) {
            if (dep[top[u]] > dep[top[v]]) std::swap(u, v);
            v = fa[top[v]];
        }
        return dep[u] < dep[v] ? u : v;
    }
}

2. 整体二分算法

使用整体二分算法来解决多查询的第 $k$ 小问题：

void solve(int l, int r, int ql, int qr) {
    if (l == r || ql > qr) {
        for (int i = ql; i <= qr; i++)
            ans[q[i].id] = o[l].c;
    } else {
        int mid = (l + r) >> 1;
        // 处理权值在 [l, mid] 范围内的盘子
        // 计算每个查询包含的盘子数量
        // 根据数量将查询划分到左右两部分
        solve(l, mid, ql, pr);
        solve(mid + 1, r, pr + 1, qr);
    }
}

3. 二维数点问题

判断"盘子路径是否在水果路径内"可以转化为二维平面上的点包含问题：

• 将每个盘子路径映射为二维平面上的一个点 $(dfn[a], dfn[b])$（假设 $dfn[a] \leq dfn[b]$）
• 水果路径对应平面上的一个矩形区域
• 查询就转化为矩形内点的计数问题

namespace scan {
    struct layer { int l, r, y, k; };
    struct qry { int x, y, id; };
    
    void add(int xl, int xr, int yl, int yr) {
        // 添加矩形区域
        ly[++tl] = {xl, xr, yl, 1};
        ly[++tl] = {xl, xr, yr + 1, -1};
        ly[++tl] = {yl, yr, xl, 1};
        ly[++tl] = {yl, yr, xr + 1, -1};
    }
    
    void scan() {
        // 使用扫描线+树状数组处理矩形计数
        std::sort(ly + 1, ly + tl + 1, [](layer &a, layer &b) { return a.y < b.y; });
        std::sort(qr + 1, qr + tq + 1, [](qry &a, qry &b) { return a.y < b.y; });
        
        int j = 1;
        for (int i = 1; i <= tq; i++) {
            for (; j <= tl && ly[j].y <= qr[i].y; j++)
                BIT::add(ly[j].l, ly[j].r, ly[j].k);
            res[qr[i].id] = BIT::query(qr[i].x);
        }
    }
}

4. 路径包含判定

对于盘子路径 $(a,b)$ 和水果路径 $(u,v)$，分两种情况处理：

情况1：LCA不是端点

if (lca != o[i].a && lca != o[i].b)
    scan::add(pos[o[i].a], pos[o[i].a] + siz[o[i].a] - 1, 
              pos[o[i].b], pos[o[i].b] + siz[o[i].b] - 1);

情况2：LCA是其中一个端点

int v = lca == o[i].a ? o[i].b : o[i].a;
int u = prev(HLD::son[lca].upper_bound(pos[v]))->second;
scan::add(1, pos[u] - 1, pos[v], pos[v] + siz[v] - 1);
scan::add(pos[u] + siz[u], n, pos[v], pos[v] + siz[v] - 1);

复杂度分析

预处理：$O(n \log n)$ 的树链剖分

整体二分：$O((P + Q) \log^2 n \log C)$，其中 $C$ 是权值范围

扫描线：$O((P + Q) \log n)$ 每次整体二分

总复杂度：$O((P + Q) \log^3 n)$，在 $n, P, Q \leq 40000$ 时可接受

关键技巧

1.树链剖分：将树结构线性化，便于处理路径关系

2.整体二分：高效处理多组第 $k$ 小查询

3.二维数点：将路径包含问题转化为平面几何问题

4.扫描线+树状数组：优化矩形查询和计数

5.分类讨论：根据LCA位置不同，采用不同的矩形构造方法

总结

本题通过以下技巧解决了复杂的路径包含查询问题：

1.利用树链剖分将树结构转化为线性结构

2.使用整体二分处理多组第 $k$ 小查询

3.将路径包含关系转化为二维平面上的矩形包含关系

4.使用扫描线和树状数组高效处理矩形计数

算法能够处理 $n, P, Q \leq 40000$ 的大规模数据，是树上路径查询的经典解决方法。