DataStructure - 题解

标签与难度

标签: 树上问题, LCA, 根号分治, 树分块, Mo算法, 离线处理, 树状数组难度: 2600

题目大意喵~

主人，你好呀！这道题是这样的喵~

我们有一棵 $n$ 个节点的有根树，然后有 $m$ 次询问。每次询问会给我们三个数字 $l, r, x$ ，需要我们找出，在所有编号在 $[l, r]$ 区间内的节点中，有多少对节点 $(i, j)$ (其中 $i < j$ )，它们的最近公共祖先 (LCA) 正好是节点 $x$ 呢？

简单来说，就是对每次查询 $(l, r, x)$ ，统计满足下面条件的数对 $(i, j)$ 的数量：

$l \le i < j \le r$
$\text{LCA}(i, j) = x$

要把所有满足条件的数对都找出来哦，喵~

解题思路分析

这道题看起来有点吓人呢，查询范围是任意的，还和树的结构LCA搅在了一起，直接暴力肯定是不行的说！( $N, M$ 都是 $2 \cdot 10^5$ 级别，暴力会超时到天上去的喵！)

不过别担心，我我最喜欢的就是这种有挑战性的问题啦！我们一步一步来拆解它，呐。

核心公式：容斥原理

首先，我们来分析一下" $\text{LCA}(i, j) = x$ "这个条件。这意味着什么呢？这意味着节点 $i$ 和 $j$ 都必须在以 $x$ 为根的子树里。但仅仅这样还不够哦！如果它们都在 $x$ 的同一个孩子的子树里，那它们的LCA就会是那个孩子或者更深层的节点，而不是 $x$ 了。

所以，正确的条件是：

$i$ 和 $j$ 都在 $x$ 的子树中。
$i$ 和 $j$ 不在 $x$ 的同一个孩子的子树中。

利用容斥原理，我们可以把这个计数问题转化一下： (LCA是 $x$ 的点对数) = (两个点都在 $x$ 子树中的点对数) - (两个点都在 $x$ 的某个孩子 $c$ 的子树中的点对数之和)

设 $S(u)$ 表示节点 $u$ 的子树中的节点集合。设 $C(u, l, r)$ 表示在编号区间 $[l, r]$ 中，属于 $S(u)$ 的节点数量。那么，对于一次查询 $(l, r, x)$ ，答案就可以表示为：

\text{Ans} = \binom{C(x, l, r)}{2} - \sum_{c \in \text{children}(x)} \binom{C(c, l, r)}{2}

其中 $\binom{k}{2} = \frac{k(k-1)}{2}$ 表示从 $k$ 个元素中选出 2 个的组合数。这个公式就是我们解题的核心啦！问题就变成了如何高效地计算所有这些 $C(u, l, r)$ 的值。

根号分治：当困难无法一概而论时

直接对每个查询都计算上面那个公式还是太慢了，特别是当一个节点 $x$ 有很多很多孩子的时候。这时候，一个非常强大的思想就要登场啦——根号分治（或者叫树分块）！

我们可以把 $x$ 的孩子分成两类：

重儿子 (Heavy Children): 子树规模比较大的孩子。
轻儿子 (Light Children): 子树规模比较小的孩子。

怎么划分呢？我们可以设一个阈值 BLOCK_SIZE（比如取 $\sqrt{N}$ 左右）。

如果一个孩子 $c$ 的子树大小 size[c] > BLOCK_SIZE，我们就叫它重儿子。
否则，就是轻儿子。

一个节点最多有 $N / \text{BLOCK\_SIZE}$ 个重儿子，数量是可控的！但轻儿子可能还是很多。根据这个分类，我们把答案的计算也分成两部分：

\text{Ans} = \underbrace{\left( \binom{C(x)}{2} - \sum_{c \in \text{hson}(x)} \binom{C(c)}{2} \right)}_{\text{Part 1: 重儿子部分}} - \underbrace{\sum_{c \in \text{lson}(x)} \binom{C(c)}{2}}_{\text{Part 2: 轻儿子部分}}

这两部分可以用不同的方法来高效计算哦！

Part 1: 重儿子部分的处理 (离线 + 树状数组)

对于第一部分，我们需要计算 $C(x)$ 和 $C(c)$ (对于所有重儿子 $c$ )。一个节点 $x$ 的重儿子数量不多（最多 $N/\text{BLOCK\_SIZE}$ 个），所以对于每个查询，我们只需要计算有限个 $C(u, l, r)$ 的值。

$C(u, l, r)$ 是什么？是在编号区间 $[l, r]$ 内，且在子树 $S(u)$ 内的节点数。我们可以通过一次DFS，把树的结构拍平成一个序列（DFS序）。一个子树 $S(u)$ 就对应DFS序上的一个连续区间 [dfn[u], out[u]]。于是问题就变成了二维计数问题：统计满足 id 在 $[l, r]$ 且 dfn[id] 在 [dfn[u], out[u]] 的点的数量。

这是一个经典的二维数点问题，可以用离线处理来解决！

把查询 (l, r, u) 拆成 (r, u) 和 (l-1, u) 两个事件。
把所有事件按节点编号排序。
我们从 $1$ 到 $N$ 遍历节点编号 $i$ 。
使用一个树状数组 (BIT)，在 dfn[i] 的位置上加 1。
处理所有结束点为 $i$ 的事件：对于事件 (i, u)，在BIT上查询 [dfn[u], out[u]] 的和，就能得到 $C(u, 1, i)$ 。
C(u, l, r) = C(u, 1, r) - C(u, 1, l-1)。

这样，我们就可以高效地算出所有重儿子部分的贡献啦！

Part 2: 轻儿子部分的处理 (树上莫队)

现在轮到棘手的轻儿子部分了： $\sum_{c \in \text{lson}(x)} \binom{C(c, l, r)}{2}$ 。轻儿子可能非常多，不能像重儿子那样一个个计算。但是，查询的区间 [l, r] 是对节点编号的，这让我们想到了一个处理区间问题的强大离线算法——Mo's Algorithm (莫队算法)！

莫队算法的核心思想是通过巧妙地排序查询，使得处理区间的左右端点指针移动的总距离最小。我们需要设计一个能在 $O(1)$ 或近似 $O(1)$ 时间内处理端点移动（add 一个点, remove 一个点）的数据结构。

为了配合莫队，我们还需要对树进行一次特殊的链式分解（类似轻重链剖分，但目的不同）：

DFS预处理: 计算 fa, size, dfn, out 等。
划分重/轻儿子: 和上面一样，根据子树大小划分。
定义top数组:
- 对于根节点 rt，top[rt] = rt。
- 对于节点 u 的一个重儿子 v，它延续父亲的链，top[v] = top[u]。
- 对于节点 u 的一个轻儿子 v，它自己开启一条新链，top[v] = v。

这样，每个轻儿子都是一条链的链头。我们要求的 $\sum_{c \in \text{lson}(x)} \binom{C(c)}{2}$ 就变成了 $\sum_{c \text{是} x \text{的轻儿子}} \binom{\text{在}[l,r]\text{中且在链}c\text{及其子链中的节点数}}{2}$ 。

在莫队算法中，我们维护两个数组：

chain_node_count[t]: 记录当前 [L, R] 区间内，有多少节点属于以 t 为链头的这条链。
light_contrib[y]: 记录对于节点 y，它的所有轻儿子链的贡献和，即 $\sum_{c \in \text{lson}(y)} \binom{\text{chain\_node\_count}[c]}{2}$ 。

当莫队的指针移动，add(i) 一个节点时：

找到节点 i 所在的链的链头 t = top[i]。
找到 t 的父亲 p = fa[t]。
如果 t 是 p 的一个轻儿子 (top[t] == t)，那么 light_contrib[p] 会发生变化。我们先减去旧的贡献，再增加新的贡献。
更新 chain_node_count[t] 的值（加1）。
remove(i) 操作则完全相反。

每次 add/remove 操作都只涉及常数次计算，是 $O(1)$ 的！这样，莫队处理完一个区间 [l, r] 后，对于查询 (l, r, x)，我们直接取 light_contrib[x] 就是轻儿子部分的总贡献啦。

总结一下

好啦，整体思路就是这样喵：

预处理: DFS 得到树的基本信息，并基于子树大小进行重/轻儿子划分和链式分解 (top数组)。
Part 1 (重): 用离线+树状数组的方法，计算出 $\binom{C(x)}{2} - \sum_{c \in \text{hson}(x)} \binom{C(c)}{2}$ 。
Part 2 (轻): 用莫队算法，计算出 $\sum_{c \in \text{lson}(x)} \binom{C(c)}{2}$ 。
合并: 从 Part 1 的结果中减去 Part 2 的结果，就是最终答案啦！

这个方法结合了多种算法，是不是很酷？就像我我一样，既能优雅地散步，也能瞬间爆发出强大的力量，喵~

代码实现

下面是我根据这个思路，精心重构的代码哦！加了很多注释，希望能帮助你理解每一个细节，呐。

cpp

#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
#include <numeric>

using namespace std;

typedef long long ll;

const int MAXN = 200005;
const int BLOCK_SIZE = 450; // 根号分治的阈值

// --- 树结构 & 预处理 ---
int n, m, root;
vector<int> adj[MAXN];
int parent[MAXN], depth[MAXN], subtree_size[MAXN];
int dfn[MAXN], out[MAXN], dfn_timer;
vector<int> heavy_children[MAXN], light_children[MAXN];
int top[MAXN]; // 链头

// --- 莫队算法相关 ---
struct Query {
    int id;
    int l, r, x;
    int block_l;
};
Query queries[MAXN];
ll query_ans[MAXN];
ll light_contrib[MAXN];
int chain_node_count[MAXN];

// --- 离线+树状数组相关 ---
struct OfflineRequest {
    int query_id;
    int node_u;
    int sign; // +1 for r, -1 for l-1
};
vector<OfflineRequest> offline_requests[MAXN];
ll heavy_counts[MAXN];
int temp_heavy_counts[MAXN][MAXN / BLOCK_SIZE + 2]; // 存储C(u,l,r)的值

// --- 树状数组 ---
int bit[MAXN];

void bit_update(int idx, int delta) {
    for (; idx <= n; idx += idx & -idx) {
        bit[idx] += delta;
    }
}

int bit_query(int idx) {
    int sum = 0;
    for (; idx > 0; idx -= idx & -idx) {
        sum += bit[idx];
    }
    return sum;
}

// 组合数 C(k, 2)
ll combinations2(ll k) {
    if (k < 2) return 0;
    return k * (k - 1) / 2;
}

// 第一次DFS：计算父子关系、子树大小、深度，并划分重/轻儿子
void dfs1(int u, int p, int d) {
    parent[u] = p;
    depth[u] = d;
    subtree_size[u] = 1;
    dfn[u] = ++dfn_timer;

    for (int v : adj[u]) {
        if (v == p) continue;
        dfs1(v, u, d + 1);
        subtree_size[u] += subtree_size[v];
        if (subtree_size[v] > BLOCK_SIZE) {
            heavy_children[u].push_back(v);
        } else {
            light_children[u].push_back(v);
        }
    }
    out[u] = dfn_timer;
}

// 第二次DFS：进行链式分解，确定top数组
void dfs2(int u, int t) {
    top[u] = t;
    for (int v : heavy_children[u]) {
        dfs2(v, t); // 重儿子延续链
    }
    for (int v : light_children[u]) {
        dfs2(v, v); // 轻儿子开启新链
    }
}

// --- 莫队核心操作 ---
void add(int node_idx) {
    int t = top[node_idx];
    int p = parent[t];
    if (p != 0 && top[t] == t) { // t是p的轻儿子
        light_contrib[p] -= combinations2(chain_node_count[t]);
    }
    chain_node_count[t]++;
    if (p != 0 && top[t] == t) {
        light_contrib[p] += combinations2(chain_node_count[t]);
    }
}

void remove(int node_idx) {
    int t = top[node_idx];
    int p = parent[t];
    if (p != 0 && top[t] == t) { // t是p的轻儿子
        light_contrib[p] -= combinations2(chain_node_count[t]);
    }
    chain_node_count[t]--;
    if (p != 0 && top[t] == t) {
        light_contrib[p] += combinations2(chain_node_count[t]);
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> n >> m >> root;
    for (int i = 0; i < n - 1; ++i) {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    // --- 预处理 ---
    dfs1(root, 0, 1);
    dfs2(root, root);

    // --- 准备查询 ---
    for (int i = 0; i < m; ++i) {
        queries[i].id = i;
        cin >> queries[i].l >> queries[i].r >> queries[i].x;
        queries[i].block_l = queries[i].l / BLOCK_SIZE;

        // Part 1: 为重儿子部分准备离线请求
        offline_requests[queries[i].r].push_back({i, queries[i].x, 1});
        if (queries[i].l > 1) {
            offline_requests[queries[i].l - 1].push_back({i, queries[i].x, -1});
        }
        for (size_t j = 0; j < heavy_children[queries[i].x].size(); ++j) {
            int hc = heavy_children[queries[i].x][j];
            offline_requests[queries[i].r].push_back({i, hc, 1});
            if (queries[i].l > 1) {
                offline_requests[queries[i].l - 1].push_back({i, hc, -1});
            }
        }
    }

    // --- Part 1: 离线处理重儿子部分 ---
    for (int i = 1; i <= n; ++i) {
        bit_update(dfn[i], 1);
        for (const auto& req : offline_requests[i]) {
            int u = req.node_u;
            int count_in_subtree = bit_query(out[u]) - bit_query(dfn[u] - 1);
            if (u == queries[req.query_id].x) {
                heavy_counts[req.query_id] += req.sign * count_in_subtree;
            } else {
                // 找到u是x的哪个重儿子
                for (size_t j = 0; j < heavy_children[queries[req.query_id].x].size(); ++j) {
                    if (heavy_children[queries[req.query_id].x][j] == u) {
                        temp_heavy_counts[req.query_id][j] += req.sign * count_in_subtree;
                        break;
                    }
                }
            }
        }
    }

    for (int i = 0; i < m; ++i) {
        query_ans[i] += combinations2(heavy_counts[i]);
        int x = queries[i].x;
        for (size_t j = 0; j < heavy_children[x].size(); ++j) {
            query_ans[i] -= combinations2(temp_heavy_counts[i][j]);
        }
    }

    // --- Part 2: 莫队处理轻儿子部分 ---
    sort(queries, queries + m, [](const Query& a, const Query& b) {
        if (a.block_l != b.block_l) {
            return a.block_l < b.block_l;
        }
        return (a.block_l & 1) ? (a.r < b.r) : (a.r > b.r);
    });

    int current_l = 1, current_r = 0;
    for (int i = 0; i < m; ++i) {
        int l = queries[i].l, r = queries[i].r, x = queries[i].x;
        while (current_l > l) add(--current_l);
        while (current_r < r) add(++current_r);
        while (current_l < l) remove(current_l++);
        while (current_r > r) remove(current_r--);
        
        query_ans[queries[i].id] -= light_contrib[x];
    }

    // --- 输出答案 ---
    for (int i = 0; i < m; ++i) {
        cout << query_ans[i] << "\n";
    }

    return 0;
}

复杂度分析

这只我来给你分析一下时间和空间复杂度哦~

时间复杂度:
- 预处理: 两次DFS都是 $O(N)$ 的。
- Part 1 (重儿子): 我们遍历所有节点一次，用树状数组更新和查询。树状数组操作是 $O(\log N)$ 。每个查询会产生 $1 + |\text{hson}|$ 个离线请求。由于 $|\text{hson}| \le N/\text{BLOCK\_SIZE}$ ，总请求数是 $O(M \cdot N/\text{BLOCK\_SIZE})$ 。总时间是 $O(N \log N + M \cdot (N/\text{BLOCK\_SIZE}) \cdot \log N)$ 。如果 BLOCK_SIZE 取 $\sqrt{N}$ ，这部分是 $O((N + M\sqrt{N})\log N)$ 。
- Part 2 (轻儿子): 莫队算法。排序是 $O(M \log M)$ 。指针移动的总次数是 $O(N\sqrt{M})$ 或 $O((N+M)\sqrt{N})$ ，取决于块大小。每次add/remove是 $O(1)$ 的。所以这部分是 $O((N+M)\sqrt{N})$ 。
- 总复杂度: 两者相加，为 $O((N+M)\sqrt{N} + (N + M\sqrt{N})\log N)$ 。在 $N,M$ 同阶时，可以看作是 $O(N\sqrt{N})$ 。这对于 $2 \cdot 10^5$ 的数据规模是可以通过的！
空间复杂度:
- 树的邻接表、各种预处理数组（parent, dfn, top 等）都是 $O(N)$ 。
- 离线请求和莫队查询数组是 $O(M)$ 。
- 树状数组是 $O(N)$ 。
- 总空间复杂度是 $O(N+M)$ 的说。

知识点总结

这道题真是一次精彩的冒险，喵~ 我们用到了好多有趣的工具呢！

容斥原理: 这是解决组合计数问题的基本武器，将复杂条件转化为简单条件的加减。
根号分治 (Square Root Decomposition): 当问题的不同规模部分具有不同性质时，这是一个超级有用的思想。我们把问题一分为二，用最适合的方法分别解决，就像猫咪有时用爪子挠，有时用牙齿咬一样~
树上莫队: 将莫队算法和树的链式分解结合，处理树上路径/子树和外部区间结合的复杂查询。
离线处理: 将所有查询读入后，重新排序以方便处理，是解决很多在线算法难以解决的问题的法宝。
树状数组 (Fenwick Tree): 高效处理单点更新和前缀和查询的利器，是离线二维数点问题的标准配件。

希望这篇题解能帮到你哦！如果还有不明白的地方，随时可以再来问我，我随时待命，喵~

DataStructure - 题解 ​

标签与难度 ​

题目大意喵~ ​

解题思路分析 ​

核心公式：容斥原理 ​

根号分治：当困难无法一概而论时 ​

Part 1: 重儿子部分的处理 (离线 + 树状数组) ​

Part 2: 轻儿子部分的处理 (树上莫队) ​

总结一下 ​

代码实现 ​

复杂度分析 ​

知识点总结 ​