当前位置：首页 > news >正文

DAY 13

news 2026/6/13 1:20:07

DAY 13

某些题解

树

直径

树上任意两节点之间最长的简单路径即为树的「直径」。

sol1

两次DFS

从任意点 \(z\) 开始做DFS，找出距离最远的点 \(x\) 。
从 \(x\) 开始做DFS，找出离 \(x\) 最远的点 \(y\) 。

\(x\) 到 \(y\) 就是直径，需要证明，第一次DFS找到的点必是直径的一端。反证法讨论即可。

此方法简单但是不适用于负边权。

sol2

树形DP

记录每个结点向下走，通过两个不同的儿子能走到的最远距离 \(d1\) 和次远距离 \(d2\) （若儿子数量不足则记为0），那么每个点的 \(d1 + d2\) 的最大值就是直径。

此方法稍微复杂一些但是适用于存在负边权的场景。

算法流程：

考虑一个点 \(u\) ，初始化 \(d1[u] = d2[u] = 0\)
遍历所有的儿子 \(v\)
递归计算出儿子的值 \(d1[v], d2[v]\)
用 \(d1[v] + w_{u,v}\) 来更新 \(d[u]\)

消防

某个国家有 \(n\) 个城市，这 \(n\) 个城市中任意两个都连通且有唯一一条路径，每条连通两个城市的道路的长度为 \(z_{i}\)。

现在这个国家的经费足以在一条边长度和不超过 \(s\) 的路径（两端都是城市）上建立消防枢纽，为了尽量提高枢纽的利用率，要求其他所有城市到这条路径的距离的最大值最小。

你受命监管这个项目，你当然需要知道应该把枢纽建立在什么位置上。

\[1\leq n\leq 3\times 10^{5},\quad 1\leq z_{i}\leq 10^{3}. \]

sol

如果只选一个点，那么它必然是直径上一点。

因为离这个点最远的点必然是直径的一端，把当前点往直径上移动，答案不会变得更差。

如果还要扩展当前点，路径上其他点也必然在直径上。

简单证明即可。

所以我们先得出直径，它是一条链，答案就是这条链上的一个区间，相当于一个窗口。

计算这个窗口到其他点的最远距离。

窗口的两端，最远到直径的两端
窗口内部，可以用BFS预处理出来

每个窗口对应的路径的距离最大值用单调队列计算即可，答案取最小值，复杂度 \(O(n)\)。

重心

如果在树中选择某个节点并删除，这棵树将分为若干棵子树，统计子树节点数并记录最大值。取遍树上所有节点，使此最大值取到最小的节点被称为整个树的重心。

性质：

树的重心如果不唯一，则至多有两个，且这两个重心相邻。
以树的重心为根时，所有子树的大小都不超过整棵树大小的一半。
树中所有点到某个点的距离和中，到重心的距离和是最小的；如果有两个重心，那么到它们的距离和一样。
把两棵树通过一条边相连得到一棵新的树，那么新的树的重心在连接原来两棵树的重心的路径上。
在一棵树上添加或删除一个叶子，那么它的重心最多只移动一条边的距离。

医院设置

树上每个点都住了 \(a_{i}\) 个居民，现在要选一个点作为医院，求所有居民到医院的距离之和的最小值。

要求时间复杂度 \(O(n)\)

sol

带点权的重心

考虑把 \(u\) 作为医院，能够一次DFS算出来此时的最小距离和。

考虑把医院从 \(u\) 移动到一个孩子 \(v\) ，此时 \(v\) 整颗子树上所有人去医院的距离都减一，其他人去医院的距离加一，记 \(sz_{v}\) 为以 \(v\) 为根的子树的点权和，该值可以在第一次DFS时顺便算出：

\[f[v] = f[u] - sz_{v} + (sum - sz_{v}) \]

第二次DFS换根DP即可。

哈夫曼树

树的带权路径长度

设二叉树具有 \(n\) 个带权叶结点，从根结点到各叶结点的路径长度与相应叶节点权值的乘积之和称为树的带权路径长度（Weighted Path Length of Tree, WPL）。

设 \(w_{i}\) 为二叉树第 \(i\) 个叶结点的权值， \(l_{i}\) 为从根结点到第 \(i\) 个叶结点的路径长度，则WPL计算公式如下：

\[WPL = \sum_{i = 1}^{n} w_{i} l_{i} \]

构造方法：

将每个点当做一颗独根二叉树加入集合。
每次从集合取出根权值最小的两颗二叉树合并，构造成新的二叉树，新的根的权值为原本两根权值之和，将新的二叉树加入集合。
重复直到集合中剩余一棵树

简单证明：权值最小的两个叶结点总是最深的叶结点，并且将这两个结点调整为兄弟结点至少不会破坏编码树的最优性。

最优前缀码

根据词频构造哈夫曼树，再标上01即可，叶子上的01串即为最优前缀码。

证明：计算一个词编码后的长度期望即可。

荷马史诗

给出一篇文章，文章包含 \(n\) 个单词，已知它们的出现次数，构造一种 \(k\) 进制的前缀码，计算编码文章后的最短长度。

sol

构造一个 \(k\) 叉哈夫曼树即可。

注意：当 \((n - 1)\bmod (k - 1)\neq 0\) 时，需要补上一些权值为0的点。

二叉排序树

Binary Sort Tree、二叉查找树、二叉搜索树（Binary Search Tree）、BST

二叉搜索树是一种二叉树的树形数据结构，其定义如下：

空树是二叉搜索树。
若二叉搜索树的左子树不为空，则其左子树上所有点的附加权值均小于其根节点的值。
若二叉搜索树的右子树不为空，则其右子树上所有点的附加权值均大于其根节点的值。
二叉搜索树的左右子树均为二叉搜索树。

树上操作的复杂度均为 \(O(h)\) ， \(h\) 是树的高度 \(O(\log n)\sim O(n)\)

代码实现

节点信息

int lc[100005], rc[100005];
int val[100005];
int sz[100005], cnt[100005];
int root;
int tot;

遍历

中序遍历即可

找最值

int findMin(int o) {if (!lc[o]) return val[o];return findMin(lc[o]);
}
int findMax(int o) {if (!rc[o]) return val[o];return findMax(rc[o]);
}

查找目标点 \(k\) 是否在树中

bool search(int o, int v) {if (!o) return 0;if (v == val[o]) return 1;if (v > val[o]) return search(rc[o], v);if (v < val[o]) return search(lc[o], v);
}

插入一个元素 \(v\)

void insert(int& o, int v) {if (!o) {o = ++tot;val[o] = v;lc[o] = rc[o] = 0;siz[o] = cnt[o] = 1;return;}siz[o]++;if (v == val[o]) cnt[o]++;if (v > val[o]) insert(rc[o], v);if (v < val[o]) insert(lc[o], v);
}

删除一个元素 \(v\)

int deleteMin(int& o) {if (!lc[o]) {int u = o;o = rc[o];return u;}int u = deleteMin(lc[o]);size[o] -= cnt[u];return u;
}void del(int& o, int v) {size[o]--;if (val[o] == v) {if (cnt[o] > 1) {cnt[o]--;return;}if (lc[o] && rc[o]) {int s = deleteMin(rc[o]);cnt[o] = cnt[s];val[o] = val[s];} else {o = lc[o] + rc[o];}return;}if (val[o] > v) del(lc[o], v);if (val[o] < v) del(rc[o], v);
}

求元素 \(v\) 的排名

int queryrnk(int o, int v) {if (!o) return 1;if (val[o] == v) return size[lc[o]] + 1;if (val[o] > v) return queryrnk(lc[o], v);if (val[o] < v) return queryrnk(rc[o], v) + size[lc[o]] + cnt[o];
}

求排第 \(k\) 名的元素

int querykth(int o, int k) {if (siz[lc[o]] >= k) return querykth(lc[o], k);if (siz[lc[o]] < k - cnt[o]) return querykth(rc[o], k - siz[lc[o]] - cnt[o]);return val[o];
}

求前驱或后继

int querypre(int o, int v) {int ans = -inf;if (val[o] < v) ans = val[o];if (val[o] >= v && lc[o]) ans = max(ans, querypre(lc[o], v));if (val[o] < v && rc[o]) ans = max(ans, querypre(rc[o], v));return ans;
}int querybck(int o, int v) {int ans = inf;if (val[o] > v) ans = val[o];if (val[o] > v && lc[o]) ans = min(ans, querybck(lc[o], v));if (val[o] <= v && rc[o]) ans = min(ans, querybck(rc[o], v));return ans;
}

【深基16.例7】普通二叉树（简化版）

模板题

【模板】普通平衡树

模板题，但是操作数变多。

平衡树

极端情况下树退化为一条链，操作的复杂度变成了 \(O(n)\)

由此引出了平衡树，通过一定操作维持树的高度（平衡性）来降低操作的复杂度。

关于一棵搜索树是否「平衡」，不同的平衡树中对「平衡」有着不同的定义，在OI中我们一般定义为：以T为根节点的树，每一个结点的左子树和右子树高度差最多为1。

有非常多实现方式。

LCA

最近公共祖先（Lowest Common Ancestor）

用处非常广泛，比如计算机中两点的距离： \(dis(x,y) = dis(x,lca) + dis(lca,y)\)

朴素求法

将两个点中深度大的点先向上移动 \(u = fa[u]\) ，直到两点的深度一致。
若两点目前还未相遇，两点同时向上移动。

复杂度 \(O(h)\) ，最差 \(O(n)\)

倍增

向上移动 \(d\) 步时，不一步一步移动，而是一次移动 \(2^{i}\) 步，当 \(i\in range(0,\log_2d)\) 时，一定能覆盖全部情况。需要预处理出每个结点 \(u\) 向上移动 \(2^{i}\) 步后的点 \(f[u][i]\)

\[f[u][0] = fa[u] \]

\[f[u][i] = f[f[u][i - 1]][i - 1] \]

若是带边权的树，也可以预处理出每个结点 \(u\) 向上移动 \(2^{i}\) 步需要走的边权和 \(d[u][i]\)

\[d[u][0] = w[fa][u] \]

\[d[u][i] = d[u][i - 1] + d[f[u][i - 1]][i - 1] \]

【模板】最近公共祖先（LCA）

模板

for (int i = 2; i <= cnt; i++)lg[i] = lg[i >> 1] + 1;

任选一点开始DFS，预处理出其他信息

void dfs(int u, int f) {dep[u] = dep[u] + 1;fa[u][0] = f;for(int i = 1; i <= lg[n]; i++) {if((1<<i) > dep[u]) break;fa[u][i] = fa[fa[u][i-1]][i-1];}for(int i = 0; i < tree[u].size(); i++) {if(tree[u][i] == f) continue;dfs(tree[u][i], u);}
}

计算LCA

int lca(int x, int y) {if(dep[x] > dep[y]) swap(x, y);int d = dep[y] - dep[x];for(int i = lg[d]; i >= 0; i--) {if(d & (1<<i)) y = fa[y][i];}if(x == y) return x;for(int i = lg[n]; i >= 0; i--) {if(fa[x][i] == fa[y][i]) continue;x = fa[x][i], y = fa[y][i];}return fa[x][0];
}

[NOIP2013提高组]货车运输

A国有 \(n\) 座城市，编号从1到 \(n\) ，城市之间有 \(m\) 条双向道路。每一条道路对车辆都有重量限制，简称限重。现在有 \(q\) 辆货车在运输货物，司机们想知道每辆车在不超过车辆限重的情况下，最多能运多重的货物。 \(1\leq n< 10^{4}\) ， \(1\leq m< 5\times 10^{4}\) ， \(1\leq q< 3\times 10^{4}\) ， \(0\leq z\leq 10^{5}\)。

显然在不破坏连通性的基础上，删掉边权最小的边不会使得答案变得更差，所以先跑一个最大生成树。题目要计算的就是两点之间路径上边权的最小值。在模板的基础上，预处理出每个结点 \(u\) 向上移动 \(2^{i}\) 步需要走的经过的边权最小值 \(d[u][i]\) ：

\[d[u][0] = w[fa][u] \]

\[d[u][i] = \min(d[u][i-1], d[fa[u][i-1]][i-1]) \]

RMQ问题

Range Maximum/Minimum Query，区间最大（最小）值。

在接下来的描述中，默认初始数组大小为 \(n\) ，询问次数为 \(m\) 。

在接下来的描述中，默认时间复杂度标记方式为 \(O(A)\sim O(B)\) ，分别表示预处理时间复杂度和单次询问的时间复杂度。

单调栈

把全部的询问按照右端点排序，对于 \([l,r]\) 这个询问，将下标 \(\leq r\) 的点全部入栈，栈内点具有单调性，二分查出下标第一个大于等于 \(l\) 的点即可。

时间 \(O(m\log m)\sim O(\log n)\)

空间 \(O(n)\)

线段树

时间 \(O(n)\sim O(\log n)\)

空间 \(O(n)\)

ST表

基于倍增思想，类比刚刚的LCA，预处理出 \(i\) 点开始往后 \(2^{j}\) 个点的区间 \([i,i + (1<<j) - 1]\) 内的最值 \(st[i][j]\) 。

\[st[i][0] = a[i] \]

\[st[i][j] = \max\{st[i][j - 1], st[i + 2^{j - 1}][j - 1]\} \]

查找 \([l,r]\) 时，找出两个区间，分成两个部分，再求最值即可。

int query(int l, int r) {int k = lg[r - l + 1];return max(st[l][k], st[r - (1 << k) + 1][k]);
}

时间 \(O(n\log n)\sim O(1)\)

空间 \(O(n)\)

代码简单，在线，查找速度快，不支持修改。

【模板】ST表&&RMQ问题

模板题

+1/-1RMQ

在两两元素之差只差1的序列做RMQ。

RMQ只关心元素相对大小，做一个差分。

将序列分成若干个块，每个块大小为 \(\log n\) ，跑一次ST表，预处理复杂度 \(O(n / \log n \cdot \log n) = O(n)\)

对于不完整的部分，它们是一段长度不超过 \(\log n\) 的01串，可以对于全部的情况暴力预处理一个结果，复杂度

\[O(\sum_{i = 1}^{\log n}) = O(n) \]

【模板】最近公共祖先(LCA) - RMQ与LCA

对一棵树进行DFS，无论是第一次访问还是回溯，每次到达一个结点时都将编号记录下来，可以得到一个长度为 \(2n - 1\) 的序列，这个序列被称作这棵树的欧拉序列。

同时记录每个点 \(u\) 在欧拉序列的最小下标 \(p(u)\)

显然在欧拉序列中， \(lca(u,v)\) 一定出现在 \(p(u),p(v)\) 之间，这里假设 \(dfn[u] < dfn[v]\)

并且更上层的祖先没有出现在这段区间，那么 \(lca(u,v)\) 是这一段中深度最小的点。

把欧拉序列看做 \((u, dep[u])\) 这样的键值对，ST表解决即可

此时预处理复杂度为 \(O(n\log n)\) ，查找两点的LCA复杂度可以优化为 \(O(1)\)

欧拉序列的值是一个 \(+1 / -1\) 序列，预处理复杂度更优。

RMQ转LCA

把序列最小值作为根，左边的全部元素作为左子树，右边全部元素作为右子树，左右子树递归建树。

笛卡尔树

每个结点是一个 \((idx, a[idx])\) 的键值对，从键来看，符合BST的性质，从值来看，符合堆的性质。

【模板】笛卡尔树

模板

sol

如何建树，考虑已经对 \(a[1] \sim a[i - 1]\) 建树，现在把 \(a[i]\) 加入。

只对最右链有影响。

右链是单调的，单调栈解决。

for (int i = 1; i <= n; i++) {int k = top;while (k > 0 && h[stk[k]] > h[i]) k--;if (k) rs[stk[k]] = i;if (k < top) ls[i] = stk[k + 1];stk[++k] = i;top = k;
}

复杂度 \(O(n)\)

考虑原本序列上的一个区间 \([l,r]\) ，在这个区间的最小值就是 \(a[lca(l,r)]\)