【蓝桥杯 2025 省 A 扫地机器人】题解-一条长河网

题目链接

如果 $\forall t[i] = 0$ ，直接输出 $0$ 。

由于题中所给是 $n$ 个点 $n$ 条边的 连通图，我们可以得到这是一棵基环树。

我们把答案分为三类：

以环上某点 $i$ 为根的树的直径；
从某个树的叶子出发到达环上的根 $i$ ，绕过整个环，回到 $i$ ，再走向 $i$ 的另一个儿子直到叶子；
从某个树的叶子出发到达环上的根 $i$ ，不绕过 整个环，走到环上另一点 $j$ ，再走向 $j$ 的一个儿子直到叶子。

首先，我们找到基环树的环，环长为 $m$ ，然后对于每颗树，都预处理出 $\rm{mdep[i]}$ 和 $\rm{sdep[i]}$ ，分别表示以 $i$ 为根的树的深度最大值和次大值，这个一次 $\rm{dfs}$ 就能做到。

然后对于长度为 $m$ 的环，设顺时针（或逆时针）第 $i$ 个点为 $\rm{vec[i]}, \ i \in [0, m)$ ，我们破环成链，令 $\rm{vec[i + m] = vec[i]}$ ，再做一个前缀和，即

$\rm{s[i + 1] = s[i] + t[vec[i]]}, \ i \in [0, 2m).$

这样三类的答案就分别是：

第一类：
$\rm{mdep[i] + sdep[i] + t[i]}, \ \forall i \in [0, n).$
第二类：
$\rm{mdep[vec[i]] + sdep[vec[i]] + s[m], \ \forall i \in [0, m)}.$
第三类：
$\rm{mdep[vec[i]] + (s[i + 1] - s[j]) + mdep[vec[j]]}, \ 0 \leq j < i < 2m, \ i - j < m.$

第一、二类要求最大值直接 $O (n)$ 遍历即可，第三类则需要对式子变形，变为

$\rm{(mdep[vec[i]] + s[i + 1]) + (mdep[vec[j]] - s[j])},$

这样一来对每个 $i$ ，就只要维护 $\rm{mdep[vec[j]] - s[j]}$ 的最大值，其中

$\rm{j \in [\max(0, i - m + 1), \ i),}$

这可以用单调队列实现，时间复杂度 $O (n)$ 。

时间复杂度 $O (n)$

C++ Code

#include <bits/stdc++.h>template<class T>
std::istream &operator>>(std::istream &is, std::vector<T> &v) {for (auto &x: v) {is >> x;}return is;
}
template<class T>
void chmax(T &a, T b) {if (a < b) {a = b;}
}int main() {std::ios::sync_with_stdio(false);std::cin.tie(nullptr);int n;std::cin >> n;std::vector<int> t(n);std::cin >> t;if (std::ranges::count(t, 0) == n) {std::cout << 0 << "\n";return 0;}std::vector<std::vector<int>> adj(n);for (int i = 0; i < n; i++) {int u, v;std::cin >> u >> v;u--, v--;adj[u].push_back(v);adj[v].push_back(u);}int idx = 0;std::vector<int> vec;vec.reserve(n);std::vector<bool> ins(n);std::vector<bool> cyc(n);std::vector<int> dfn(n, -1);std::vector<int> pre(n, -1);auto init = [&](auto &&self, int x) -> void {dfn[x] = idx++;ins[x] = true;for (int y: adj[x]) {if (y == pre[x]) {continue;}if (dfn[y] == -1) {pre[y] = x;self(self, y);} else if (ins[y]) {for (int i = x; ; i = pre[i]) {vec.push_back(i);cyc[i] = true;if (i == y) {break;}}}}ins[x] = false;};init(init, 0);std::vector<int> mdep(n);std::vector<int> sdep(n);std::ranges::fill(pre, -1);auto tree = [&](auto &&self, int x) -> void {for (int y: adj[x]) {if (y == pre[x] or cyc[y]) {continue;}pre[y] = x;self(self, y);if (mdep[x] < mdep[y] + t[y]) {sdep[x] = mdep[x];mdep[x] = mdep[y] + t[y];} else if (sdep[x] < mdep[y] + t[y]) {sdep[x] = mdep[y] + t[y];}}};int res = 0;for (int i: vec) {tree(tree, i);chmax(res, mdep[i] + sdep[i]);}int dia = 0;for (int i = 0; i < n; i++) {chmax(dia, mdep[i] + sdep[i] + t[i]);}int m = vec.size();vec.insert(vec.end(), vec.begin(), vec.end());std::vector<int> s(2 * m + 1);for (int i = 0; i < 2 * m; i++) {s[i + 1] = s[i] + t[vec[i]];}int ans = std::max(dia, res + s[m]);std::deque<int> q;for (int i = 0; i < 2 * m; i++) {int j = vec[i];while (not q.empty() and i - q.front() >= m) {q.pop_front();}if (not q.empty()) {chmax(ans, mdep[j] + s[i + 1] + mdep[vec[q.front()]] - s[q.front()]);}while (not q.empty() and mdep[vec[q.back()]] - s[q.back()] <= mdep[j] - s[i]) {q.pop_back();}q.push_back(i);}std::cout << ans << "\n";return 0;
}

题目链接

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

C++ Code

相关文章：

时间复杂度 $O (n)$