题目 3346: 

蓝桥杯2025年第十六届省赛真题-扫地机器人

时间限制: 2s 内存限制: 192MB 提交: 110 解决: 24

题目描述

在一个含有 n 个点 n 条边的无重边无自环的连通无向图中，有一个扫地机 器人在执行清扫作业，其中结点 i 的标记 ti ∈ {0, 1} 如果为 1 ，则说明该结点需 要进行清扫，扫地机器人在到达这个结点时会顺便进行清扫工作。机器人想知 道，如果选定任意结点出发，每条边只能经过一次的话，最多能清扫多少个待 清扫结点？

输入格式

输入的第一行包含一个正整数 n 。 第二行包含 n 个整数 t1, t2, · · · , tn ，相邻整数之间使用一个空格分隔。 接下来 n 行，每行包含两个正整数 ui , vi ，用一个空格分隔，表示结点 ui 和结点 vi 之间有一条边。

输出格式

输出一行包含一个整数表示答案。

样例输入

9
1 0 1 0 0 1 1 0 1
2 8
2 9
2 5
1 5
1 3
1 4
4 5
4 6
6 7

样例输出

4

提示

【样例说明】 

其中一种路线：3 → 1 → 4 → 6 → 7 。 

【评测用例规模与约定】 对于 20% 的评测用例，1 ≤ n ≤ 5000 ； 

对于所有评测用例，1 ≤ n ≤ 500000 ，ti ∈ {0, 1} ，1 ≤ ui , vi ≤ n 。

我们说一下思路，一看数据规模1e5的级别了，考虑的时间复杂度最多也只能是o（nlogn）级别，当然也可以是o(n),显然爆搜一定会爆炸的，我们得找方法，观察到其n个结点n条边，那么一定有且只有一个环，那么其实这个图就是一个基环树，我们的主要想法就是先把这个环找出来，将整个图看作是一个环，环上各个结点挂着各自的子树，我们计算环上每个结点的最大分支贡献值，最终答案无非三种情况：

1.不走环，走环上某个结点的两条分支，那么这种情况需要计算啥，很明显环上结点分支的次大贡献值得找出来吧

2.树-环-树，这个过程看着简单实际还是有些难的，因为我们需要考虑在找环时不能只知道环上结点有啥，还需知道环的顺序，为啥呢？假如说我现在选定两个环上结点 i 与 j 更新ans，那么就让ans比较一下 i的分支最大贡献加上j的分支最大贡献还得加上从i到j过程中的贡献（顺时针走还是逆时针都要考虑），这个过程显然是需要知道从i到j都经过哪些结点的，所以必须知道环的顺序，咋求呢？可以拓扑排序先找出来在环中的结点，在任意选择一个环中结点作为起点，开始便历其他环中结点，这样就自带顺序了。除了这个想要快速计算从i到j的贡献还需要前缀和辅助不是吗，不然如果环太大，还是会超时，当然还有一个难点，就是我总不难去便历选择i和j来求出最大值吧，那样还是炸，那么怎么办呢？用单调队列+滑动窗口维护，那么具体按啥值来维护呢，我们待会贴完代码再讲

3.同一个结点走一圈再回到这个结点走它的次大分支，那么一个显而易见的结论就出现了，第三种情况一定优于第一种情况，因此我们最终无需考虑第一种情况， 但是我代码考虑了

给出code：

#include <bits/stdc++.h>

using namespace std;

static const int N = 5e5 + 5;

int n;

int a[N];                 // 节点权值 (0/1)

int h[N], to[N << 1], nxt[N << 1], cnt = 1;

bool vis[N], in[N];       // in: 是否在环上

int stk[N << 1], tp;      // 存环

int f[N], g[N];           // 树 DP

int pre[N << 1];          // 环前缀和

int q[N << 1];            // 单调队列

int ans = 0;

inline void add_edge(int u, int v) {

    to[++cnt] = v;

    nxt[cnt] = h[u];

    h[u] = cnt;

}

// 找环：返回值用于回溯标记环

int dfs_find_cycle(int x, int fr) {

    vis[x] = true;

    for (int i = h[x]; i; i = nxt[i]) {

        int y = to[i];

        if ((i ^ 1) == fr) continue;

        if (!vis[y]) {

            int ret = dfs_find_cycle(y, i);

            if (ret == 0) continue;

            if (ret == -1) return -1;

            stk[++tp] = y;

            in[y] = true;

            if (ret == x) return -1;

            return ret;

        } else {

            stk[++tp] = y;

            in[y] = true;

            return y;

        }

    }

    return 0;

}

// 树 DP（不走环）

void dfs_tree(int x, int fa) {

    f[x] = g[x] = a[x];

    for (int i = h[x]; i; i = nxt[i]) {

        int y = to[i];

        if (y == fa || in[y]) continue;

        dfs_tree(y, x);

        g[x] = max(g[x], f[x] + f[y]);

        ans = max(ans, f[x] + f[y]);

        f[x] = max(f[x], a[x] + f[y]);

    }

    ans = max(ans, f[x]);

}

int main() {

    ios::sync_with_stdio(false);

    cin.tie(nullptr);

    cin >> n;

    for (int i = 1; i <= n; i++) cin >> a[i];

    for (int i = 1; i <= n; i++) {

        int u, v;

        cin >> u >> v;

        add_edge(u, v);

        add_edge(v, u);

    }

    // 1. 找环

    dfs_find_cycle(1, 0);

    // 2. 环复制一份，方便滑窗

    for (int i = 1; i <= tp; i++) stk[i + tp] = stk[i];

    // 3. 前缀和（环权值）

    for (int i = 1; i <= tp * 2; i++) {

        pre[i] = pre[i - 1] + a[stk[i]];

    }

    // 4. 对每个环点做树 DP

    for (int i = 1; i <= tp; i++) {

        dfs_tree(stk[i], 0);

        f[stk[i]] -= a[stk[i]]; // 去掉自身，避免重复

    }

    // 5. 环上 DP（子树 → 环 → 子树）

    int head = 1, tail = 0;

    for (int i = 1; i <= tp * 2; i++) {

        while (head <= tail && q[head] <= i - tp) head++;

        if (head <= tail) {

            ans = max(ans,

                      f[stk[i]] + f[stk[q[head]]] +

                      pre[i] - pre[q[head] - 1]);

        }

        while (head <= tail &&

               f[stk[i]] - pre[i - 1] >=

               f[stk[q[tail]]] - pre[q[tail] - 1]) {

            tail--;

        }

        q[++tail] = i;

    }

    // 6. 同一环点：子树A → 绕一圈 → 子树B

    for (int i = 1; i <= tp; i++) {

        ans = max(ans, g[stk[i]] + pre[tp] - a[stk[i]]);

    }

    cout << ans << "\n";

    return 0;

}

给出一些数组的解释

✅ f[x]

从 x 出发，向下走的一条“单链”能拿到的最大清扫点数

• 必须是一条连续路径

• 只能选 一个子树方向

• 用来“往外接”

---

✅ g[x]

路径经过 x，左右各选一个分支时的最大值

• 可以同时用 两个子树

• 但不能再往上接

• 只用于更新答案 ans

ok，接着刚才的二的思路，我们着重讲讲加红代码

一、先一句话说清：这段代码在干啥

它在所有“连续的环段”里，找：
左树 + 环段 + 右树 的最大值

---

二、把代码翻译成数学式

你这句是核心：

ans = max(ans, f[stk[i]] + f[stk[q[head]]] + pre[i] - pre[q[head] - 1]);

对应数学含义：

• i：环段右端点

• j = q[head]：环段左端点

• pre[i] - pre[j-1]：
  👉 环上从 j 到 i 的连续一段

所以整体是：

f[right] + f[left] + 环段(left → right)

---

三、那为啥要“复制环 + 限制 i - j < tp”？

原因只有一个：

不能走完整个环

所以：

while (q[head] <= i - tp) head++;

意思是：

如果区间长度 ≥ tp
👉 这段环走了一整圈
👉 不合法，扔掉

---

四、关键变形（这一步最重要）

我们把目标式子拆一下：

f[i] + f[j] + pre[i] - pre[j - 1]

整理一下（只为方便看）：

= (f[i] + pre[i]) + (f[j] - pre[j - 1])

💥 重点来了

• 对于固定的 i

• 你要选一个 j

• 让 (f[j] - pre[j - 1]) 最大

👉 这就是单调队列要维护的东西