「NOI2022」树上邻域数点

longxiaoxin @ 2025-11-30 18:20:42

题意回顾

我们有一棵 $n$ 个点的有根树，每条边 $e = (u,v)$ 对应一个信息 $\iota(e)$ ，包含：

边集合 $\{e\}$
点集合 $\{u,v\}$

有两种合并操作：

$R(a,b)$ ：边集为 $S_E(a) \cup S_E(b)$ ，点集为 $S_V(a)$
$C(a,b)$ ：边集为 $S_E(a) \cup S_E(b)$ ，点集为 $S_V(a) \oplus S_V(b)$

合并条件：两个信息的边集不能相交，点集必须恰好相交一个点。

对于询问 $(u,d)$ ，要求构造一个信息 $o$ ，使得：

$S_E(o)$ 包含 $u$ 的 $d$ -邻域内的所有边
调用 $MR$ / $MC$ 的次数 ≤ $M$

核心思路

1. 问题转化

我们需要快速求出以 $u$ 为中心、半径为 $d$ 的连通子图的所有边。

关键观察：

最终信息的点集可以是该连通子图中的任意两个点
我们需要一种能快速"拼凑"出任意连通子图的方法

2. 点分治框架

使用点分树（动态树分治）来预处理：

对原树进行点分治，建立点分树
对于每个重心 $c$ $c$ ，预处理：
- $c$ 到子树内所有点的路径信息
- 按深度分层存储

3. 信息存储设计

对每个重心 $c$ ，我们存储：

$f_c(v)$ ： $c$ 到 $v$ 路径上所有边的合并信息（点集为 $\{c,v\}$ ）
按 $v$ 到 $c$ 的距离分组存储

这样，对于 $c$ 子树内的任意点集，我们可以通过合并这些路径信息来构造。

算法步骤

步骤 1：预处理点分树

void build_centroid_tree(int u) {
    // 标记 u 为已访问
    vis[u] = true;
    
    // 计算 u 到子树内所有点的信息
    vector<info> depth_info[MAX_DEPTH];
    dfs_collect(u, -1, 0, emptyinfo, depth_info);
    
    // 递归处理子树
    for (int v : adj[u]) {
        if (!vis[v]) {
            // 找到连通块的重心
            int center = find_centroid(v);
            build_centroid_tree(center);
        }
    }
}

步骤 2：收集路径信息

void dfs_collect(int u, int fa, int dep, info cur, vector<info> depth_info[]) {
    // 合并当前边信息
    if (fa != -1) {
        info edge = get_edge_info(u, fa);
        cur = MR(cur, edge);  // 或 MC，根据点集需求
    }
    
    depth_info[dep].push_back(cur);
    
    for (int v : adj[u]) {
        if (v != fa && !vis[v]) {
            dfs_collect(v, u, dep + 1, cur, depth_info);
        }
    }
}

步骤 3：回答询问

对于询问 $(u,d)$ ：

在点分树上从 $u$ 开始向上跳
对每个祖先重心 $c$ $c$ ：
- 如果 $u$ 在 $c$ 的某棵子树中，且该子树完全包含在 $u$ 的 $d$ -邻域内
- 则直接取预处理的该子树信息
合并这些子树信息

info query(int u, int d) {
    if (d == 0) return emptyinfo;
    
    info res = emptyinfo;
    int x = u;
    
    // 在点分树上跳
    while (x != -1) {
        int dist = get_distance(x, u);
        if (dist <= d) {
            // 获取 x 子树中深度不超过 d - dist 的所有信息
            info subtree_info = get_subtree_info(x, d - dist);
            if (!isempty(res)) {
                // 找到公共点进行合并
                res = merge_with_common_point(res, subtree_info);
            } else {
                res = subtree_info;
            }
        }
        x = parent_in_centroid_tree[x];
    }
    
    return res;
}

步骤 4：带公共点的合并

关键技巧：保证合并的两个信息共享一个公共点。

info merge_with_common_point(info a, info b) {
    // 找到 a 和 b 的点集中的公共点
    // 这需要在预处理时精心设计点集
    
    // 方法1：如果 a 和 b 有公共点，直接用 MR 或 MC
    // 方法2：通过中间信息引入公共点
    
    // 示例：假设我们知道 p 是公共点
    info path_to_p = get_path_to_point(p);
    info temp = MC(a, path_to_p);  // 让 temp 包含 p
    return MR(temp, b);  // 合并 temp 和 b，它们都包含 p
}

复杂度分析

预处理：
- 点分治： $O(n \log n)$
- 每个点被处理 $O(\log n)$ 次
- 总 $MR$ / $MC$ 调用： $O(n \log n)$
单次询问：
- 在点分树上跳 $O(\log n)$ 次
- 每次最多 $O(1)$ 次 $MR$ / $MC$ 调用
- 总调用： $O(\log n)$

满足 $M \ge 5$ 时通常可过。

实现细节

1. 点集设计

预处理时要保证任意两个需要合并的信息都有公共点：

通常选择重心作为公共点
或者选择路径的端点

2. 边界处理

$d = 0$ 时直接返回 emptyinfo
注意树链的情况可以特殊优化

3. 内存管理

info 类型变量占用固定 12 字节
避免同时存在过多 info 变量

代码框架

#include "count.h"
#include <vector>
#include <algorithm>
using namespace std;

const int MAXN = 200005;
vector<int> adj[MAXN];
vector<info> edge_info[MAXN];
bool vis[MAXN];
int sz[MAXN];
int parent_in_centroid_tree[MAXN];

// 预处理每个重心的信息
struct CentroidInfo {
    vector<vector<info>> depth_info;  // depth_info[i] 存储深度为 i 的所有信息
    // 其他必要信息...
} centroid_data[MAXN];

void dfs_size(int u, int fa) {
    sz[u] = 1;
    for (int v : adj[u]) {
        if (v != fa && !vis[v]) {
            dfs_size(v, u);
            sz[u] += sz[v];
        }
    }
}

int find_centroid(int u, int fa, int total) {
    for (int v : adj[u]) {
        if (v != fa && !vis[v] && sz[v] > total / 2) {
            return find_centroid(v, u, total);
        }
    }
    return u;
}

void dfs_collect(int u, int fa, int dep, info cur, vector<info> depth_info[]) {
    if (fa != -1) {
        // 获取边 (u, fa) 的信息
        info e;
        for (int i = 0; i < adj[u].size(); i++) {
            if (adj[u][i] == fa) {
                e = edge_info[u][i];
                break;
            }
        }
        cur = MR(cur, e);
    }
    
    if (depth_info[dep].empty()) {
        depth_info[dep].push_back(cur);
    } else {
        // 合并同深度的信息
        depth_info[dep][0] = MR(depth_info[dep][0], cur);
    }
    
    for (int v : adj[u]) {
        if (v != fa && !vis[v]) {
            dfs_collect(v, u, dep + 1, cur, depth_info);
        }
    }
}

void build_centroid_tree(int u) {
    dfs_size(u, -1);
    int cent = find_centroid(u, -1, sz[u]);
    vis[cent] = true;
    
    // 收集信息
    vector<info> depth_info[MAXN];
    dfs_collect(cent, -1, 0, emptyinfo, depth_info);
    
    // 存储到 centroid_data[cent]
    
    for (int v : adj[cent]) {
        if (!vis[v]) {
            int sub_cent = find_centroid(v, -1, sz[v]);
            parent_in_centroid_tree[sub_cent] = cent;
            build_centroid_tree(sub_cent);
        }
    }
}

void init(int T, int n, int q, vector<int> fa, vector<info> e, int M) {
    // 建图
    for (int i = 0; i < n - 1; i++) {
        int u = fa[i], v = i + 2;
        adj[u].push_back(v);
        adj[v].push_back(u);
        edge_info[u].push_back(e[i]);
        edge_info[v].push_back(e[i]);
    }
    
    // 构建点分树
    fill(vis, vis + n + 1, false);
    fill(parent_in_centroid_tree, parent_in_centroid_tree + n + 1, -1);
    build_centroid_tree(1);
}

info ask(int u, int d) {
    if (d == 0) return emptyinfo;
    
    // 在点分树上跳，合并信息
    info res = emptyinfo;
    int x = u;
    
    while (x != -1) {
        // 计算距离并获取对应信息
        // 具体实现依赖于预处理的数据结构
        
        x = parent_in_centroid_tree[x];
    }
    
    return res;
}

总结

本题是一道结合树分治和信息合并的构造题，关键点在于：

使用点分治预处理树的结构信息
精心设计点集保证合并时有公共点
分层存储信息快速回答邻域查询
合理使用 $MR$ / $MC$ 在调用次数限制内完成构造

算法标签：树的分治、树上倍增

ID

5691

时间

1000ms

内存

256MiB

难度

标签

递交数

已通过

上传者

longxiaoxin

1 条题解