「CEOI2019」动态直径

0
zhoujinchong2004 @ 2025-10-26 12:14:13
一、问题分析

1.1 问题描述

给定一棵 $n$ 个节点的带权树，需要支持 $q$ 次操作，每次修改一条边的权值，并查询修改后树的直径。

树的直径定义：树上任意两点间距离的最大值。

关键约束：
- 强制在线：每次查询的结果会影响下一次操作
- 数据范围： $n, q \le 10^5$ ，边权 $w \le 2 \times 10^{13}$
1.2 核心难点
1. 动态性：边权会被修改，需要快速更新直径
2. 在线性：无法离线处理所有查询
3. 复杂度：朴素算法每次 $O(n^2)$ 求直径，总复杂度 $O(qn^2)$ 无法接受
二、算法思路

2.1 关键观察

观察1：树的直径可以表示为两个节点到它们 LCA 的距离之和。

对于树上两点 $u$ 和 $v$ ，设 $\text{dis}[u]$ 为节点 $u$ 到根的距离，它们之间的距离为：
$$\text{dist}(u, v) = \text{dis}[u] + \text{dis}[v] - 2 \cdot \text{dis}[\text{lca}(u, v)] $$
观察2：使用欧拉序（DFS序）将树转换为序列，子树对应连续区间。

通过欧拉序，可以将树上问题转换为序列问题，从而使用线段树等数据结构。

观察3：修改一条边的权值，等价于给其子树中所有节点的 $\text{dis}$ 值加上一个增量。

2.2 算法框架
1. 预处理：通过 DFS 构建欧拉序，记录每个节点在欧拉序中的出现区间
2. 线段树维护：维护五个关键值来支持快速查询直径
3. 区间更新：修改边权时，对对应子树的欧拉序区间进行更新
三、数学推导

3.1 欧拉序的构造

在 DFS 遍历树时：
- 每次进入节点时记录一次该节点
- 递归完所有子树后，再记录一次父节点
这样每个节点会被记录多次，但整个子树在欧拉序中形成连续区间。

性质：节点 $u$ 的子树在欧拉序中对应区间 $[\text{t1}[u], \text{t2}[u]]$ 。

3.2 线段树维护值的含义

为了高效计算树的直径，线段树需要维护以下五个值：
1. mx[p]：区间内所有节点到根的距离的最大值
  $$\text{mx}[p] = \max_{i \in [l, r]} \text{dis}[\text{rev}[i]] $$
2. mn[p]：区间内所有节点到根的距离的最小值
  $$\text{mn}[p] = \min_{i \in [l, r]} \text{dis}[\text{rev}[i]] $$
3. lx[p]：区间的"左贡献值"，表示从左侧延伸的路径的最大贡献
4. rx[p]：区间的"右贡献值"，表示从右侧延伸的路径的最大贡献
5. ans[p]：区间内的直径
3.3 线段树合并（pushup）的数学原理

对于线段树节点 $p$ ，其左子节点为 $\text{ls}(p)$ ，右子节点为 $\text{rs}(p)$ 。

3.3.1 mx 和 mn 的合并

这两个值的合并是直观的：
$$\text{mx}[p] = \max(\text{mx}[\text{ls}(p)], \text{mx}[\text{rs}(p)]) $$$$\text{mn}[p] = \min(\text{mn}[\text{ls}(p)], \text{mn}[\text{rs}(p)]) $$
3.3.2 lx 的合并推导

$\text{lx}[p]$ 表示：对于经过区间 $p$ 且左端点在区间内的路径，其贡献的最大值。

设路径的两个端点为 $u$ 和 $v$ ，其中 $u$ 在左侧区间内， $v$ 可能在左侧、右侧或外部。

路径长度为：
$$\text{dist}(u, v) = \text{dis}[u] + \text{dis}[v] - 2 \cdot \text{dis}[\text{lca}(u, v)] $$
对于固定的 $v$ ，我们希望最大化：
$$\text{dis}[u] - 2 \cdot \text{dis}[\text{lca}(u, v)] $$
情况1：路径完全在左子区间内
- 贡献为 $\text{lx}[\text{ls}(p)]$
情况2：路径完全在右子区间内
- 贡献为 $\text{lx}[\text{rs}(p)]$
情况3：路径跨越左右子区间
- 左端点 $u$ 在左子区间，取 $\text{dis}[u]$ 最大，即 $\text{mx}[\text{ls}(p)]$
- 右端点 $v$ 在右子区间，它们的 LCA 在分界处或更上方
- 欧拉序的性质保证：右子区间的最小值 $\text{mn}[\text{rs}(p)]$ 对应的节点是右子树的根，也是左侧节点与右侧节点的 LCA
- 贡献为 $\text{mx}[\text{ls}(p)] - 2 \cdot \text{mn}[\text{rs}(p)]$
因此：
$$\text{lx}[p] = \max\{\text{lx}[\text{ls}(p)], \text{lx}[\text{rs}(p)], \text{mx}[\text{ls}(p)] - 2 \cdot \text{mn}[\text{rs}(p)]\} $$
3.3.3 rx 的合并推导

类似地， $\text{rx}[p]$ 表示右端点在区间内的路径的最大贡献：
$$\text{rx}[p] = \max\{\text{rx}[\text{ls}(p)], \text{rx}[\text{rs}(p)], \text{mx}[\text{rs}(p)] - 2 \cdot \text{mn}[\text{ls}(p)]\} $$
3.3.4 ans 的合并推导

区间 $p$ 的直径可能来自三种情况：

情况1：直径完全在左子区间内
- 答案为 $\text{ans}[\text{ls}(p)]$
情况2：直径完全在右子区间内
- 答案为 $\text{ans}[\text{rs}(p)]$
情况3：直径的两个端点分别在左右子区间
- 子情况3.1：左端点在左子区间，右端点在右子区间
  
  左端点的最大贡献： $\text{lx}[\text{ls}(p)]$
  
  右端点的距离： $\text{mx}[\text{rs}(p)]$
  
  总距离： $\text{lx}[\text{ls}(p)] + \text{mx}[\text{rs}(p)]$
- 子情况3.2：右端点在右子区间，左端点在左子区间
  
  左端点的距离： $\text{mx}[\text{ls}(p)]$
  
  右端点的最大贡献： $\text{rx}[\text{rs}(p)]$
  
  总距离： $\text{mx}[\text{ls}(p)] + \text{rx}[\text{rs}(p)]$
因此：
$$\text{ans}[p] = \max\{\text{ans}[\text{ls}(p)], \text{ans}[\text{rs}(p)], \text{lx}[\text{ls}(p)] + \text{mx}[\text{rs}(p)], \text{mx}[\text{ls}(p)] + \text{rx}[\text{rs}(p)]\} $$
3.4 懒标记的处理

当给区间加上增量 $k$ 时（即修改边权），需要更新：
- $\text{mx}[p] \leftarrow \text{mx}[p] + k$ （距离增加）
- $\text{mn}[p] \leftarrow \text{mn}[p] + k$ （距离增加）
- $\text{lx}[p] \leftarrow \text{lx}[p] - k$ （因为 $\text{lx}$ 定义中有 $-2 \cdot \text{dis}$ ，增加 $k$ 相当于减去 $k$ ）
- $\text{rx}[p] \leftarrow \text{rx}[p] - k$ （同理）
- $\text{ans}[p]$ 不变（直径是相对距离，区间整体加 $k$ 不影响）
推导：设路径长度为 $\text{dist}(u, v) = \text{dis}[u] + \text{dis}[v] - 2 \cdot \text{dis}[\text{lca}]$

如果给区间内所有节点的 $\text{dis}$ 都加 $k$ ：
- 新的路径长度：$(\text{dis}[u] + k) + (\text{dis}[v] + k) - 2 \cdot (\text{dis}[\text{lca}] + k) = \text{dis}[u] + \text{dis}[v] - 2 \cdot \text{dis}[\text{lca}]$
- 路径长度不变！
但对于 $\text{lx}$ 和 $\text{rx}$ ：
- $\text{lx}$ 中包含 $\text{dis}[u] - 2 \cdot \text{dis}[\text{lca}]$
- 如果 $u$ 在区间内加 $k$ ，而 $\text{lca}$ 可能在外部不变，则 $\text{lx}$ 的值会改变
- 但在我们的实现中，由于区间对应子树， $\text{lca}$ 必然在区间内，所以变化量为 $k - 2k = -k$
四、代码模块详解

模块 1：全局定义与宏
```
#include <bits/stdc++.h>
#define int long long
#define ls(p) p<<1
#define rs(p) p<<1|1
#define mid ((l+r)>>1)
#define pb(a,b,c,d) (q[a].push_back({b,c,d}))
using namespace std;
const int N = 2e5 + 9, M = 8e5 + 9;
```
说明：
- int 定义为 long long 处理大数据
- ls(p) 和 rs(p) 为线段树左右子节点
- mid 为区间中点
- pb 为添加边的宏
- N 为节点数上限，M 为欧拉序长度上限（每个节点可能被访问多次）
模块 2：数据结构定义
```
int n, m, dis[N], dfn[M], len[N], rev[M], t1[N], t2[N], pos[N];
struct Node {
    int ft, sd, id;
};
vector<Node>q[N];
int tot;
```
变量说明：
- dis[x]：节点 $x$ 到根的距离
- rev[i]：欧拉序第 $i$ 位置对应的节点编号
- t1[x]：节点 $x$ 在欧拉序中第一次出现的位置
- t2[x]：节点 $x$ 的子树在欧拉序中的右边界
- pos[i]：第 $i$ 条边的子节点（修改时更新其子树）
- len[i]：第 $i$ 条边的当前权值
- tot：欧拉序的当前长度
模块 3：构建欧拉序（DFS）
```
void dfs(int x, int f) {
    rev[++tot] = x, t1[x] = tot, dfn[x] = tot;

    for (auto i : q[x]) {
        if (i.ft == f)
            continue;

        dis[i.ft] = dis[x] + i.sd, dfs(i.ft, x), pos[i.id] = i.ft;
        rev[++tot] = x;
    }

    t2[x] = tot;
}
```
算法流程：
1. 进入节点 $x$ 时，记录到欧拉序：rev[++tot] = x
2. 标记节点 $x$ 第一次出现的位置：t1[x] = tot
3. 遍历所有子节点：
  
  计算子节点到根的距离：dis[i.ft] = dis[x] + i.sd
  
  递归访问子节点
  
  记录边对应的子节点：pos[i.id] = i.ft
  
  递归完成后，再次记录父节点：rev[++tot] = x
4. 标记节点 $x$ 子树的右边界：t2[x] = tot
关键性质：
- 节点 $x$ 的子树在欧拉序中对应区间 $[\text{t1}[x], \text{t2}[x]]$
- 修改边 $(x, y)$ 的权值时，需要更新 $y$ 的子树，即区间 $[\text{t1}[y], \text{t2}[y]]$
时间复杂度： $O(n)$

模块 4：线段树维护结构
```
int mx[M], mn[M], lx[M], rx[M], ans[M], tag[M];
```
数组说明：
- mx[p]：线段树节点 $p$ 对应区间的最大距离
- mn[p]：线段树节点 $p$ 对应区间的最小距离
- lx[p]：左贡献值
- rx[p]：右贡献值
- ans[p]：区间直径
- tag[p]：懒标记，表示区间加法的增量
模块 5：线段树合并（pushup）
```
void pushup(int p) {
    mx[p] = max(mx[ls(p)], mx[rs(p)]);
    mn[p] = min(mn[ls(p)], mn[rs(p)]);
    lx[p] = max(max(lx[ls(p)], lx[rs(p)]), mx[ls(p)] - 2 * mn[rs(p)]);
    rx[p] = max(max(rx[ls(p)], rx[rs(p)]), mx[rs(p)] - 2 * mn[ls(p)]);
    ans[p] = max(max(ans[ls(p)], ans[rs(p)]), max(lx[ls(p)] + mx[rs(p)], mx[ls(p)] + rx[rs(p)]));
}
```
功能：根据子节点信息更新父节点信息。

数学依据：见第三章"数学推导"部分。

时间复杂度： $O(1)$

模块 6：懒标记操作
```
void addtag(int p, int k) {
    tag[p] += k, mx[p] += k, mn[p] += k, lx[p] -= k, rx[p] -= k;
}

void pushdown(int p) {
    addtag(ls(p), tag[p]), addtag(rs(p), tag[p]), tag[p] = 0;
}
```
addtag 功能：给节点 $p$ 打上懒标记 $k$ ，表示区间所有值加 $k$ 。

更新规则：
- mx 和 mn 增加 $k$
- lx 和 rx 减少 $k$ （因为定义中有 $-2 \cdot \text{dis}$ ）
- ans 不变（相对距离）
pushdown 功能：将懒标记下传到子节点。

时间复杂度： $O(1)$

模块 7：线段树构建
```
void build(int p, int l, int r) {
    if (l == r) {
        addtag(p, dis[rev[l]]);
        return;
    }

    build(ls(p), l, mid), build(rs(p), mid + 1, r), pushup(p);
}
```
功能：初始化线段树，叶子节点存储对应节点到根的距离。

时间复杂度： $O(n)$

模块 8：区间更新
```
void update(int p, int l, int r, int x, int y, int k) {
    if (x <= l && r <= y) {
        addtag(p, k);
        return;
    }

    pushdown(p);

    if (x <= mid)
        update(ls(p), l, mid, x, y, k);

    if (y > mid)
        update(rs(p), mid + 1, r, x, y, k);

    pushup(p);
}
```
功能：给区间 $[x, y]$ 所有值加 $k$ 。

算法流程：
1. 如果当前区间完全包含在 $[x, y]$ 内，打懒标记并返回
2. 否则，下传懒标记
3. 递归更新左右子区间
4. 更新当前节点信息
时间复杂度： $O(\log n)$

模块 9：主函数
```
signed main() {
    int u, v, w, x, y, la = 0;
    scanf("%lld %lld %lld", &n, &m, &w);

    for (int i = 1; i < n; i++)
        scanf("%lld %lld %lld", &u, &v, &len[i]), pb(u, v, len[i], i), pb(v, u, len[i], i);

    dfs(1, 0), build(1, 1, tot);

    while (m--) {
        scanf("%lld %lld", &x, &y), x = (x + la) % (n - 1) + 1, y = (y + la) % w;
        update(1, 1, tot, t1[pos[x]], t2[pos[x]], y - len[x]), len[x] = y, la = ans[1];
        printf("%lld\n", la);
    }

    return 0;
}
```
算法流程：

步骤1：读入树的结构
- 读入 $n-1$ 条边
- 建立无向图（双向边）
步骤2：预处理
- 调用 dfs(1, 0) 构建欧拉序
- 调用 build(1, 1, tot) 初始化线段树
步骤3：处理查询
- 读入加密后的数据 $d, e$
- 解密： $d' = (d + \text{last}) \bmod (n-1) + 1$ ， $e' = (e + \text{last}) \bmod w$
- 修改第 $d'$ 条边的权值为 $e'$ ：
  
  计算增量： $\Delta = e' - \text{len}[d']$
  
  更新子树：update(1, 1, tot, t1[pos[d']], t2[pos[d']], Δ)
  
  更新边权：len[d'] = e'
- 查询当前直径：ans[1]（线段树根节点的答案）
- 输出并更新 last
时间复杂度： $O(q \log n)$

五、复杂度分析

5.1 时间复杂度

预处理：
- DFS 构建欧拉序： $O(n)$
- 线段树构建： $O(n)$
- 总计： $O(n)$
单次查询：
- 区间更新： $O(\log n)$
- 查询答案： $O(1)$ （直接读取根节点）
- 总计： $O(\log n)$
总时间复杂度： $O(n + q \log n)$

对于 $n, q \le 10^5$ ，约 $10^5 + 10^5 \times 17 \approx 1.7 \times 10^6$ 次操作，可以轻松通过。

5.2 空间复杂度

数组空间：
- 欧拉序： $O(n)$ （每个节点最多被记录常数次）
- 线段树： $O(n)$ （ $4n$ 个节点）
- 其他辅助数组： $O(n)$
总空间复杂度： $O(n)$

七、总结

7.1 核心思想

本题采用的欧拉序 + 线段树的核心思想：
1. 问题转化：树上问题 → 序列问题（通过欧拉序）
2. 子树对应区间：子树在欧拉序中形成连续区间
3. 线段树维护：维护五个关键值，支持区间更新和全局查询
4. 数学建模：将树的直径表示为距离和 LCA 的函数

ID

4133

时间

1000ms

内存

256MiB

难度

标签

递交数

已通过

上传者

zhoujinchong2004

1 条题解

一、问题分析

1.1 问题描述

1.2 核心难点

二、算法思路

2.1 关键观察

2.2 算法框架

三、数学推导

3.1 欧拉序的构造

3.2 线段树维护值的含义

3.3 线段树合并（pushup）的数学原理

3.3.1 mx 和 mn 的合并

3.3.2 lx 的合并推导

3.3.3 rx 的合并推导

3.3.4 ans 的合并推导

3.4 懒标记的处理

四、代码模块详解

模块 1：全局定义与宏

模块 2：数据结构定义

模块 3：构建欧拉序（DFS）

模块 4：线段树维护结构

模块 5：线段树合并（pushup）

模块 6：懒标记操作

模块 7：线段树构建

模块 8：区间更新

模块 9：主函数

五、复杂度分析

5.1 时间复杂度

5.2 空间复杂度

七、总结

7.1 核心思想

信息

还没有账户？

登录