题目理解

我们有一棵模板树，通过 $M$ 次操作构建一棵大树：

• 初始时大树就是模板树
• 每次操作：选择模板树中一个节点 $a$ 为根的子树，复制后挂到大树中节点 $b$ 下面
• 新加入的节点按照模板树中的顺序重新编号

我们需要回答 $Q$ 个询问：大树中两个节点之间的距离。

关键观察

1. 大树的结构特征

大树是由模板树的多个副本通过"链接"组成的：

• 每次操作添加一个模板树子树的副本
• 新副本通过一条边连接到已有的某个节点
• 整个大树形成一个树形结构，每个节点要么属于模板树原始副本，要么属于某个操作添加的副本

2. 节点编号的规律

如果初始模板树有 $N$ 个节点，经过 $i$ 次操作后：

• 第 $i$ 次操作添加的节点编号范围是 $[L_i+1, L_i+C_i]$，其中：
  • $L_i$ 是操作前大树的节点数
  • $C_i$ 是模板树中以 $a_i$ 为根的子树大小

3. 问题的核心挑战

直接存储整个大树是不可行的（节点数可能达到 $N \times (M+1)$），必须利用模板树的重复结构。

解法思路

算法框架：两棵树 + 映射

我们维护两棵树：

1. 模板树：原始的小树
2. 操作树：描述副本之间连接关系的树

数据结构设计

1. 模板树预处理

• 深度 $depth[]$
• 父节点 $parent[][]$（倍增LCA）
• DFS序 $dfn[]$、子树大小 $size[]$
• LCA相关预处理

2. 操作树节点

每个操作对应操作树中的一个节点，包含：

• $root$：该副本在模板树中对应的根节点
• $link$：该副本挂到大树中的哪个节点（属于之前的某个副本）
• 节点编号范围 $[L, R]$

3. 节点映射

对于大树中的任意节点 $x$，我们需要知道：

• 它属于哪个副本（操作树节点）
• 它在模板树中对应的原始节点

具体算法步骤

步骤1：预处理模板树

// 预处理深度、父节点、DFS序等
void dfs_template(int u, int fa) {
    depth[u] = depth[fa] + 1;
    parent[0][u] = fa;
    dfn[u] = ++timer;
    size[u] = 1;
    for (int v : template_tree[u]) {
        if (v == fa) continue;
        dfs_template(v, u);
        size[u] += size[v];
    }
}

步骤2：构建操作树

struct OperationNode {
    int root;      // 模板树中的根
    int link;      // 挂到大树中的哪个节点
    long long L, R; // 该副本节点编号范围
};

vector<OperationNode> ops;
long long current_size = N;  // 初始大小

for (int i = 0; i < M; i++) {
    int a, b;
    cin >> a >> b;
    
    OperationNode op;
    op.root = a;
    op.link = b;
    op.L = current_size + 1;
    op.R = current_size + size[a];
    
    ops.push_back(op);
    current_size += size[a];
}

步骤3：节点定位

给定大树节点 $x$，找到它所属的副本和对应的模板节点：

pair<int, int> locate(long long x) {
    if (x <= N) {
        return {0, x};  // 属于初始副本，模板节点就是x
    }
    
    // 二分找到x属于哪个操作
    int l = 0, r = M - 1;
    while (l <= r) {
        int mid = (l + r) / 2;
        if (ops[mid].L <= x && x <= ops[mid].R) {
            // 计算在模板树中的对应节点
            long long offset = x - ops[mid].L;
            // 需要在模板树中找到DFS序第offset+1个节点
            int template_node = find_kth_node(ops[mid].root, offset + 1);
            return {mid + 1, template_node};  // 操作编号从1开始
        } else if (x < ops[mid].L) {
            r = mid - 1;
        } else {
            l = mid + 1;
        }
    }
    return {-1, -1};  // 不会发生
}

步骤4：距离计算

计算大树中两个节点 $u$, $v$ 的距离：

1. 定位：找到 $u$, $v$ 各自所属的副本和模板节点
2. 情况分析：
   • 如果属于同一副本：直接计算模板树中的距离
   • 如果属于不同副本：需要找到它们在大树LCA副本，然后拼接路径

long long query(long long u, long long v) {
    auto [op_u, node_u] = locate(u);
    auto [op_v, node_v] = locate(v);
    
    if (op_u == op_v) {
        // 同一副本，直接计算模板树距离
        return dist_in_template(node_u, node_v);
    }
    
    // 不同副本，找到LCA副本
    int lca_op = lca_in_operation_tree(op_u, op_v);
    
    // u到其LCA副本的链接点
    long long dist1 = dist_to_link(op_u, node_u, lca_op);
    // v到其LCA副本的链接点  
    long long dist2 = dist_to_link(op_v, node_v, lca_op);
    // LCA副本内两个链接点的距离
    long long dist3 = dist_between_links(lca_op, op_u, op_v);
    
    return dist1 + dist2 + dist3;
}

关键函数实现

在子树中找第k个节点

int find_kth_node(int root, long long k) {
    // 通过DFS序在root子树中找第k个节点
    // 预处理时已经计算了每个节点的子树大小，可以二分查找
    int u = root;
    while (true) {
        if (k == 1) return u;
        k--;
        
        for (int v : template_tree[u]) {
            if (v == parent[0][u]) continue;
            if (k <= size[v]) {
                u = v;
                break;
            } else {
                k -= size[v];
            }
        }
    }
}

操作树LCA

// 操作树也是树形结构，可以预处理LCA
void build_operation_tree() {
    // 操作树：节点0是初始副本，节点1..M是操作副本
    // 每个操作节点i连接到locate(ops[i].link)找到的副本
    for (int i = 1; i <= M; i++) {
        auto [parent_op, _] = locate(ops[i-1].link);
        op_parent[0][i] = parent_op;
        op_depth[i] = op_depth[parent_op] + 1;
    }
    
    // 倍增预处理
    for (int j = 1; j < LOG; j++) {
        for (int i = 0; i <= M; i++) {
            op_parent[j][i] = op_parent[j-1][op_parent[j-1][i]];
        }
    }
}

复杂度分析

• 预处理：
  • 模板树：$O(N \log N)$
  • 操作树：$O(M \log M)$
• 每次查询：$O(\log N + \log M)$
• 总复杂度：$O((N+M+Q) \log (N+M))$，可以处理$10^5$规模

样例分析

以题目样例为例：

• 模板树：5个节点
• 操作1：复制节点4的子树挂到节点3下
• 操作2：复制节点3的子树挂到节点2下

查询(6,9)：

• 节点6属于操作1副本，对应模板节点4
• 节点9属于操作2副本，对应模板节点2
• 需要找到它们在大树中的LCA，然后拼接路径

总结

这道题的核心思想是：

1. 分层处理：将大树分解为模板树副本和操作树
2. 节点映射：通过二分和DFS序建立大树节点到模板节点的映射
3. 路径拼接：在不同副本间计算距离时，通过操作树LCA来拼接路径

通过这种"两棵树+映射"的方法，我们避免了直接处理可能巨大的树结构，而是利用模板树的重复性来高效解决问题。

算法标签：树、LCA、二分、DFS序、倍增法、节点映射