2025蓝桥杯C++ A组省赛 题解

昨天打完蓝桥杯本来想写个 $python$ $A$ 组的题解，结果被队友截胡了。今天上课把 $C++A$ 组的题看了，感觉挺简单的，所以来水一篇题解。

这场 $B$ 是一个爆搜，$C$ 利用取余的性质比较好写，$D$ 是个猜猜题，当然如果模拟也是可以的，$EG$ 是数学，$FH$ 需要预处理。$H$ 是基环树，需要拓扑排序+单调队列维护区间最大值。

$python$ 和 $c++$ 相比，我觉得 $c++$ 组的题要更简单（可能也有我 $python$ 不太熟悉的原因）。$python$ 组全是暴力，我还暴力苦手，最后三题分别是爆搜剪枝，单调栈优化+并查集，反悔贪心。 $c++$ 组只有 $B$ 是暴力，大部分是偏思维和算法，打多了 $acm$ 当然会觉得简单一些。

因为没有 $OJ$，所以我也不能保证思路和代码一定正确，仅当作参考，欢迎斧正。

2025蓝桥杯python A组题解

注：A-H在洛谷测试全部通过，但是洛谷民间数据较弱，不排除会有bug

---

A 寻找质数

题面：

第 $2025$ 个质数是多少？

思路：

直接从小到大暴力枚举每一个数，判断是否是素数，到第 $2025$ 个停止就可以了。

$n$ 个数里大概有 $\frac{n}{\ln n}$ 个数是素数，$\ln n$ 大概也就是十几，所以不需要担心越界问题。

code：

#include <iostream>
#include <cstdio>
#include <vector>
using namespace std;vector<int> primes;
bool check(int n){if(n==1)return false;for(int i=2;i*i<=n;i++)if(n%i==0)return false;return true;
}int main(){for(int i=2;primes.size()<2025;i++)if(check(i))primes.push_back(i);cout<<primes.back();return 0;
} 

---

B 黑白棋

题面：

给你一个 $6\times 6$ 的棋盘，有的位置一开始就填有棋子，其余格子需要你进行填充，要求：

1. 每一行，每一列均只有三个白棋，三个黑棋
2. 在某一行或某一列中，不能出现三个同色棋子连续的情况
3. 每一行棋子排列方式唯一，与其他行各不相同。同理每一列。行列之间不受限制。

题目保证有唯一解。按照以下格式输出答案：

黑色棋子用 $1$ 表示，白色棋子用 $0$ 表示。
从左到右、从上到下的顺序，依次遍历棋盘上的所有格子，并将这些值拼接成一个长度为 $36$ 的字符串。

思路1：

暴力枚举所有状态，然后判断状态是否成立。

枚举除了已经确定的位置以外的位置的落子情况（总共有 $26$ 个位置），每个位置只有两种情况（放白棋或者放黑棋），所以总的可能数是 $2^{26}\approx 6\times 10^8$。

枚举到一种状态后，将已经确定的位置的状态加入枚举的状态中。然后判断状态是否成立即可。

总的时间复杂度大概是 总可能数 $\times$ （加入已经确定的位置的状态 $+$ 判断），后面这个东西的时间复杂度是一个大常数，预估大概也就是 $100$。所以能跑动，就是慢一点。

code：

跑了 $139$ 秒

#include <iostream>
#include <cstdio>
#include <cstring>
#include <set>
using namespace std;
typedef long long ll;void print(string s){for(int i=0;i<6;i++,puts(""))for(int j=0;j<6;j++)cout<<s[i*6+j]<<" ";
}string b2s(ll n){//二进制转string string s;for(ll i=0;i<36;i++)s+="01"[(n>>i)&1];return s;
}
int s2b(string s){//string转二进制ll n=0;for(auto x:s)n=(n<<1)+(x-'0');return n;
}
int idx[]={0,1,3,9,16,17,26,29,31,34};
int colors[]={1,0,0,0,0,0,1,1,0,1};//1,1,1,1,1,1,1,1,1,1
string treat(string s){s=s.substr(0,26);//因为在加入10个固定位置的状态前只有26位 for(int i=0;i<10;i++){int id=idx[i];int c=colors[i];//向id上插入cs=s.substr(0,id)+(c?"1":"0")+s.substr(id);}return s;
}bool check(string s){for(int i=0;i<6;i++){int t=0;for(int j=0;j<6;j++)if(s[i*6+j]=='0')t++;if(t!=3)return false;}for(int j=0;j<6;j++){int t=0;for(int i=0;i<6;i++)if(s[i*6+j]=='0')t++;if(t!=3)return false;}for(int i=0;i<6;i++)for(int j=0;j+2<6;j++)if(s[i*6+j]==s[i*6+j+1] && s[i*6+j+1]==s[i*6+j+2])return false;for(int j=0;j<6;j++)for(int i=0;i+2<6;i++)if(s[i*6+j]==s[(i+1)*6+j] && s[(i+1)*6+j]==s[(i+2)*6+j])return false;set<string> S;for(int i=0;i<6;i++){string t;for(int j=0;j<6;j++)t+=s[i*6+j];S.insert(t);}if(S.size()!=6)return false;S.clear();for(int j=0;j<6;j++){string t;for(int i=0;i<6;i++)t+=s[i*6+j];S.insert(t);}if(S.size()!=6)return false;return true;
}int main(){for(ll i=0;i<(1<<26);i++){string t=treat(b2s(i));if(check(t)){//print(t);cout<<t;//101001010011101100010110011001100110break;}}return 0;
} 
/*
1 0 1 0 0 1
0 1 0 0 1 1
1 0 1 1 0 0
0 1 0 1 1 0
0 1 1 0 0 1
1 0 0 1 1 0*/

思路2：

爆搜剪枝

按顺序枚举每个点，尝试落子。然后加点剪枝。

这样搜的好处是可以剪枝，不像思路1需要枚举到所有的状态，因为这个题的要求条件非常苛刻，所以可以狠狠剪枝，所以速度要快很多。

思路3：

直接手玩

首先很容易发现 $(1,3)$ $(3,4)$ 只能放黑棋，否则会导致三个白棋行/列连续。

接下来假设 $(4,4)$ 放白棋，那么可以推出以下局面：

1. 因为第四列已经有三白棋，因此 $(5,4)$ $(6,4)$ 均为黑棋
2. 因为第五行已经有三黑棋，因此 $(5,1)$ $(5,2)$ $(5,5)$ 均为白棋
3. 因为第二列已经有三白棋，因此 $(2,2)$ $(3,2)$ $(4,2)$ 均为黑棋
4. 连续三黑棋，矛盾

因此 $(4,4)$ 放黑棋，从而 $(5,4)$ 放白棋，$(6,4)$ 放黑棋。

因为第六行连续两个黑棋了，$(6,3)$ 和 $(6,6)$ 只能放白棋，因此 $(6,1)$ 放黑棋。

发现 $(5,2)$ 如果放白棋，那么 $(2,2)$ $(3,2)$ $(4,2)$ 放黑棋矛盾。因此 $(5,2)$ 只能放黑棋，同理 $(2,2)$ 只能放黑棋。可以继续推出：

1. $(5,1)$ $(5,5)$ 放白棋
2. $(4,5)$ 放黑棋
3. $(4,3)$ $(4,6)$ 放白棋

继续推出：

1. $(1,6)$ $(2,6)$ 放黑棋
2. $(1,5)$ 放白棋
3. $(2,5)$ 放黑棋
4. $(2,1)$ $(2,3)$ 放白棋
5. $(3,3)$ 放黑棋
6. $(3,2)$ 放白棋，从而 $(3,1)$ 放黑棋
7. $(4,1)$ 放白棋，从而 $(4,2)$ 放黑棋
   

---

C 抽奖

题意：

抽奖机有三个转轮，每个转轮上有 $n$ 个数字图案，标号为 $1\sim n$ ，按照从 $1\sim n$ 顺序转动，当转到第 $n$ 个图案时会从第一个继续开始。奖项如下：

1. 三个相同的图案，积分 $+200$
2. 两个相同的图案，积分 $+100$
3. 三个数字图案，从左到右连续（例如 $123$ ），积分 $+200$
4. 三个数字图案，经过排序后连续，（例如 $213,321$），积分 $+100$

抽奖机处于初始状态，三个转轮都处于第一个位置。每次开始抽奖，都会产生三个对应的随机数 $x_{i1},x_{i2},x_{i3}$ ，表示第 $j$ 个转轮会向后转动 $x_{ij}$ 次停下。下次抽奖时，转轮会从上一次转动后的位置开始继续转动。

注意，一次抽奖最多只能获得一次积分，如果同时命中多个奖项，以积分最大的那个奖项为准。

请问，如果执行 $m$ 次抽奖，总积分值是多少？

$n,m\le 10^3$，$a_i,b_i,c_i\le 9$， $x_{ij}\le 1000$

思路：

把循环和取余联系起来，而不是一个一个数，就会好写很多。

code：

#include <iostream>
#include <cstdio>
using namespace std;
const int maxn=1e3+5;int n,m;
int a[3][maxn];
int p[3];int main(){cin>>n;for(int i=0;i<3;i++)for(int j=0;j<n;j++)cin>>a[i][j];cin>>m;int ans=0;for(int i=1,t;i<=m;i++){for(int i=0;i<3;i++){cin>>t;p[i]=(p[i]+t)%n;}int x[]={a[0][p[0]],a[1][p[1]],a[2][p[2]]};if(x[0]==x[1] && x[1]==x[2])ans+=200;else if(x[0]+1==x[1] && x[1]+1==x[2])ans+=200;else {if(x[0]>x[1])swap(x[0],x[1]);if(x[1]>x[2])swap(x[1],x[2]);if(x[0]>x[1])swap(x[0],x[1]);if(x[0]==x[1] || x[1]==x[2])ans+=100;if(x[0]+1==x[1] && x[1]+1==x[2])ans+=100;}}cout<<ans<<endl;return 0;
}
/*
4
3 2 4 1
2 2 2 2
4 3 0 9
3
4 4 4
3 1 1
40 39 2*/

---

D 红黑树

题意：

小蓝最近学习了红黑树，红黑树是一种特殊的二叉树，树上的结点有两种类型：红色结点和黑色结点。
小蓝在脑海中构造出一棵红黑树，构造方式如下：

1. 根结点是一个红色结点
2. 如果当前结点 $curNode$ 是红色结点，那么左子结点 $curNode.left$ 是红色结点，右子结点 $curNode.right$ 是黑色结点
3. 如果当前结点 $curNode$ 是黑色结点，那么左子结点 $curNode.left$ 是黑色结点，右子结点 $curNode.right$ 是红色结点

输入格式：

输入的第一行包含一个正整数 $m$ ，表示小蓝挑选的结点数。
接下来 $m$ 行，每行包含两个正整数 $n_i{k}_i$ ，用一个空格分隔，表示小蓝挑选的结点是第 $n_i$ 行（从上往下数）第 $k_i$ 个（从左往右数）结点。

输出格式：

输出 $m$ 行，每行包含一个字符串，依次表示小蓝每次挑选的结点的答案。RED 表示红色结点，BLACK 表示黑色结点。

数据范围：

$m\le 10$，$n_i\le 30$，$k_i\le 2^{n_i-1}$

思路：

其实仔细想想也不算神秘猜猜题。毕竟这是正了八经的完全二叉树的性质。

对一个完全二叉树，从上到下，从左到右进行编号，会有一个性质：对一个节点，编号为 $i$，那么它的左孩子节点编号为 $2i$，右孩子节点的编号为 $2i+1$。

观察一下，你很容易看出来对一个节点，它的左孩子是保持它的颜色，它的右孩子是翻转它的颜色。如果把编号看成二进制数，左孩子编号相当于在它的编号后面加一个 $0$，右孩子编号相当于在它的编号后面加一个 $1$。这说明了什么？这说明节点颜色和它编号二进制的 $1$ 的个数有关。

所以你只需要算出第 $n$ 行第 $k$ 个节点的编号，然后数一下它的二进制中 $1$ 的个数即可。

再观察一下可以发现第 $n$ 行的点只是二进制位上第 $n-1$ 位（从第零位开始算）为 $1$，除去最高位 $1$，剩余的二进制位组成的数就是 $k-1$。

code：

#include <iostream>
#include <cstdio>
using namespace std;int count(int x){int cnt=0;while(x){if(x&1)cnt++;x>>=1;}return cnt;
}int n;int main(){cin>>n;for(int i=1,_,k;i<=n;i++){cin>>_>>k;
//		cout<<k<<" "<<count(k-1)<<endl;cout<<((count(k-1)%2)?"BLACK":"RED")<<endl;}return 0;
}
/*
2
1 1
2 2*/

---

E 黑客

题意：

小蓝正在两台电脑之间拷贝数据，数据是一个 $n\times m$ 大小的正整数矩阵，因此总共有 $n\times m+2$ 个由空格分开的整数，其中前两个整数分别为 $n$ 和 $m$。然而，有黑客入侵了小蓝的电脑，导致这 $n\times m+2$ 个正整数的顺序被打乱了，小蓝想知道最多可能有多少个不同的原矩阵。

两个矩阵相同当且仅当它们行数相同、列数分别相同，且每个位置上的数相同。

输入格式：

输入的第一行包含一个正整数 $n\times m+2$ 。

第二行包含 $n\times m+2$ 个正整数 $a_1,a_2\dots a_{n\times m+2}$ ，相邻整数之间使用一个空格分隔。

输出格式：

输出一行包含一个整数表示答案。答案可能很大，请输出答案除以 1000000007 的余数。

数据范围：

$n\times m+2\le 5\times 10^5$，$a_i\le 5\times 10^5$

思路：

首先需要取出两个数作为 $n,m$。其次这个两个数肯定是 $n\times m$ 的因数（废话）。所以我们可以 $O(\sqrt{n})$ 枚举总数的因数，（如果存在这两个数）去除这两个数，并计算剩余 $n\times m$ 个数的答案。

因为矩阵相同只需要对应位置上的数相同，这个数原本的位置不重要，所以我们可以把所有数按照值统计起来。

如果原本的数各不相同，那么显然总的可能数就是 $nm$ 个数的全排列，即 $A_{nm}^{nm}=(nm)!$。如果其中有 $k$ 个数是相等的，我们就需要消除它们之间全排对整体全排列的影响。也就是除序原理。它们 $k$ 个数全排列有 $k!$ 种可能，这意味着在整体的全排列中会有 $k!$ 个其实是一种排列（因为整体在全排时把它们看作是不同的元素），所以需要在原本的基础上除以 $k!$。以此类推，对多个不同的个数大于 $1$ 的数也都是这样。

假设值为 $i$ 的数有 $cn{t}_i$ 个，那么答案就是：$$\frac{(nm)!}{{\prod }_{i}cn{t}_i!}$$

所以再预处理一下阶乘和阶乘倒数即可。

因为 $n,m$ 和 $m,n$ 算两种情况，所以在枚举因数的时候，如果因数 $p$ 和 $nm/p$ 不一致，答案需要计两遍。

算阶乘可以用 $n!=(n-1)!\ast n$ 递推，算阶乘倒数可以用 $\frac{1}{(n-1)!}=\frac{1}{n!}\ast n$ 倒推。

code：

#include <iostream>
#include <cstdio>
using namespace std;
const int maxn=5e5+5;
const int N=5e5;
typedef long long ll;
const ll mod=1e9+7;ll qpow(ll a,ll b){//a^b (%mod)ll ans=1,base=a;while(b){if(b&1)ans=ans*base%mod;base=base*base%mod;b>>=1;}return ans;
}
ll inv(ll x){return qpow(x,mod-2);
}ll nm;
ll cnt[maxn];
ll fac[maxn],ifac[maxn];int main(){fac[0]=1;for(int i=1;i<=N;i++)fac[i]=fac[i-1]*i%mod;ifac[N]=inv(fac[N]);for(int i=N;i>=1;i--)ifac[i-1]=ifac[i]*i%mod;ll ans=0;cin>>nm;for(int i=1,t;i<=nm;i++){cin>>t;cnt[t]++;}nm-=2;for(ll i=1;i*i<=nm;i++){if(nm%i!=0)continue;cnt[i]--;cnt[nm/i]--;if(cnt[i]>=0 && cnt[nm/i]>=0){
//			cout<<i<<" "<<nm/i<<endl; ll t=fac[nm];for(int j=1;j<=N;j++)t=t*ifac[cnt[j]]%mod;
//			cout<<t<<endl;ans+=t;if(i*i!=nm)ans+=t;ans%=mod;}cnt[i]++;cnt[nm/i]++;}cout<<ans;return 0;
}
/*
6
2 2 1 4 3 3*/

---

F 好串的数目

题意：

对于一个长度为n 的字符串 $s=s_0{s}_1\dots s_{n-1}$ 来说，子串的定义是从中选出
两个下标 $l,r$ （$0\le l\le r\le n-1$），这之间所有的字符组合起来的一个新的字符串：
$s’=s_l{s}_{l+1}\dots s_r$ 就是其中一个子串。

现在给出一个只有数字字符 $0\sim 9$ 组成的数字字符串，小蓝想要知道在其
所有的子串中，有多少个子串是好串。一个子串是好串，当且仅当它满足以下
两个条件之一：

1. 单字符子串一定是好串，即当子串长度为 $1$ 时，它总是好串；
2. 长度大于 $1$ 时，可以拆分为两个连续非递减子串。

其中，一个串 $p=p_0{p}_1\dots p_{k-1}$ 为连续非递减子串是指，对于所有 $1\le i<k$，满足 $p_i=p_{i-1}$ 或 $p_i=p_{i+1}+1$ 。即数字串中的每一个数字，要么等于上一个数字，要么等于上一个数字加 $1$ 。例如 $12233、456$ 是连续非递减子串。

输入格式：

输入一行包含一个字符串 $s$

输出格式：

输出一行包含一个整数表示答案，即好串的数目。

数据范围：

$1\le n\le 10^5$，$s$ 中只包含数字字符 $0\sim 9$

思路：

如果我们把整个串划分成若干段连续非递减子串，比如 $\underline{122}\underline{5}\underline{8}$。只要我们选取的区间不包含超过两个段，那么它就是一个好串。

我们可以枚举左端点，然后快速处理出右端点。其实也就是对一个左端点，我们需要知道左端点所在段的后一个段的右端点在哪里。我们可以预处理这个东西，于是就做完了。

code：

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
const int maxn=1e5+5;
typedef long long ll;int n;
string s;
int mir[maxn];int main(){cin>>s;n=s.length();s=" "+s;for(int r=n,l=n+1,lst=n+1;r>=1;r=l-1){//双指针拓展段，每次循环得到一段，段为[l,r]l--;while(l-1>=1 && (s[l]-s[l-1]==1 || s[l]-s[l-1]==0))l--;for(int i=l;i<=r;i++)mir[i]=lst;
//		cout<<l<<" "<<r<<" "<<lst<<endl;lst=r+1;}ll ans=0;for(int l=1,r,len;l<=n;l++){//右端点在[l,r)任取 r=mir[l];len=r-l;ans+=len;}cout<<ans;return 0;
}
/*
1225897856*/

---

G 地雷阵

题意：

小蓝正在平面直角坐标系中的第一象限里玩一个逃生小游戏，在第一象限中埋有 $n$ 颗地雷，第 $i$ 颗地雷的坐标为 $(x_i,y_i)$ ，触发范围为以 $(x_i,y_i)$ 为圆心，半径为 $r_i$ 的圆。一旦小蓝走进了圆内就会触发地雷导致游戏失败。小蓝初始在原点 $(0,0)$ 上，他需要在第一象限内选择一个方向一直往前走，如果能不触发任何地雷即可成功通关游戏。他想知道在 $[0,\frac{\pi }{2}]$ 中均匀随机选择一个方向，即在 $0°$ （朝向 $x$ 轴正方向）至 $90°$（朝向 $y$ 轴正方向）之间随机选择一个方向，通关游戏的概率是多少？

输入格式：

输入的第一行包含一个正整数 $n$ 。

接下来 $n$ 行，每行包含三个正整数 $x_i,y_i,r_i$，相邻整数之间使用一个空格分隔。

输出格式：

输出一行包含一个实数，四舍五入保留三位小数，表示答案。

数据范围：

$n\le 10^5$，$x_i,x_y\le 10^4$，$r_i\le min(x_i,y_i)$

思路：

$r_i\le min(x_i,y_i)$ 说明所有圆不会超出第一象限，可以少一些特殊情况判断。

如果在第一象限有一个圆，它的圆心坐标为 $(x,y)$，半径为 $r$。那么可以得到下图：

不难发现在 $[0,\frac{\pi }{2}]$ 中，$[\alpha -\theta ,\alpha +\theta ]$ 这段是不能取的，而 $\alpha =\arctan \frac{y}{x},\theta =\arcsin \frac{r}{R}=\arcsin \frac{r}{\sqrt{x^2+y^2}}$，其中 $R$ 代表从坐标原点到圆心的距离。

$n$ 个圆，那么就有 $n$ 段不能取的区间。我们取这些区间的并集，假设长度为 $len$，那么总长度为 $\frac{\pi }{2}$，不通关的概率就是 $\frac{len}{\frac{\pi }{2}}$，通关概率就是 $1-\frac{len}{\frac{\pi }{2}}$。

code：

#include <iostream>
#include <cstdio>
#include <cmath>
#include <vector>
#include <algorithm>
using namespace std;
const int maxn=1e5+5;
const double pi=acos(-1);
#define pdd pair<double,double> int n;
vector<pdd> range;int main(){cin>>n;for(int i=1;i<=n;i++){double x,y,r;cin>>x>>y>>r;double alpha=atan(y/x);double theta=asin(r/sqrt(x*x+y*y));range.push_back(pdd(alpha-theta,alpha+theta));}sort(range.begin(),range.end());double p=0,len=0;for(auto [l,r]:range){if(r<p){continue;}else if(l<p){len+=r-p;p=r;}else {len+=r-l;p=r;}}printf("%.3f",1-len/(pi/2));return 0;
}
/*
1
2 2 12
1 3 1
3 1 1*/

---

H 扫地机器人

题意：

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

输入格式：

输入的第一行包含一个正整数 $n$ 。

第二行包含 $n$ 个整数 $t_1,t_2,\dots ,t_n$，相邻整数之间使用一个空格分隔。

接下来 $n$ 行，每行包含两个正整数 $u_i,v_i$ ，用一个空格分隔，表示结点 $u_i$ 和结点 $v_i$ 之间有一条边。

输出格式：

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

数据范围：

$n\le 5\times 10^5$， t i ∈ { 0 , 1 } t_i \in \{0,1\} ti​∈{0,1}，$1\le u_i,v_i\le n$

思路：

终于是通过洛谷的数据了，这题阴的很，出题人坏的很。重构一遍发现该错的地方还是错，不是写法有问题，而是情况没讨论全。

$n$ 个点 $n$ 条边，还无重边无自环，连通图。这就是一个基环树。

基环树说白了就是在一棵树的基础上加一条边，于是变成了一种图。它存在唯一的环，环上的每个点都可以作为树根向外衍生出一棵树。因为无重边无自环，所以环长最小为 $3$。

比如这个题的样例对应的图（带圈的表示待清扫结点）：

我们的答案路径有三种情况，这就是这个题阴的地方，我们需要对每种情况进行计数，并取最大值。三种情况分别为：

1. 在以环上某点为根的一颗树内。比如上图的 $8\to 2\to 9$
2. 从某棵树的树叶开始，走到树根（树根在环上），然后走到另一个树根，再走到这棵树的树叶。比如这个样例的答案路径就是 $3\to 1\to 4\to 6\to 7$。
3. 环上某点有两个以上的儿子，以其中一个儿子所在子树开始，走到环上该点，绕环转一圈回到该点，再进入另一个儿子所在子树。

因为题目只要求边只能走一遍，但是没说点不能走多遍。阴不阴？

---

情况一和情况三都比较好处理，主要看你的实现方式。假设我们把待清理点叫做 $1$ 点。

1. 如果你用拓扑排序找环：那么找环的过程中，相当于对每棵树从叶向上遍历，那么遍历过程中顺便把某点的两个最大子树的 $1$ 点个数加起来，就得到了情况一的答案。然后枚举环上各点，将它的两个最大子树和环上的 $1$ 点个数加起来就是情况三的答案
2. 如果你用 $dfs$ 找环（这题明确就一个环，也不需要找连通分量，所以没必要上 $tarjan$，一个 $dfs$ 就解决了）：找到环后，以每个点为根，单独进行 $dfs$，直接去算情况一和情况三的答案。

---

对于情况二，如果用拓扑排序，我们可以处理出以环上某点作为起点，向环外走可达的最大 $1$ 点个数。于是我们就可以用拓扑排序来删点，边删边算上面说的东西。最后剩一下一个环。

我们可以把这个环展开，展开后有 $tn$ 个点，按顺序重新编号，假设 $a_i$ 表示第 $i$ 个点是或不是 $1$ 点，$b_i$ 表示第 $i$ 个点向环外走可达的最大 $1$ 点个数（也就是上面提到的那个东西），从某个点到另外一个点的答案就是 $b_i+a_{i+1}+a_{i+2}+\cdots +a_{j-1}+b_j$。

我们要算答案，就是要枚举左端点 $i$，然后枚举右端点 $j$，计算上面的式子，并取最大值。但是如果我们走环的另一个方向呢？比如样例中的环从 $1\to 4$ 也可以是 $1\to 5\to 4$。其实也好解决，我们将 $a,b$ 数组再循环复制一遍放到后面，这样 $i\to j$ 的另一个方向就转化为了 $j\to i+tn$，这是处理环时的常用策略，不理解可以看下面的图。

不过要注意，当我们枚举 $i$ 的时候，$j$ 的取值范围是 $[i+1,i+tn-1]$。否则区间长度大于 $tn$ 就相当于重复了。

$n\le 5\times 10^5$，怎么快速算呢。稍微处理一下上面的式子：$$\begin{array}{rl}& b_i+a_{i+1}+a_{i+2}+\cdots +a_{j-1}+b_j\\ =& a_1+\cdots +a_{j-1}+b_j-(a_1+\cdots +a_i)+b_i\end{array}$$如果我们枚举左端点 $i$，那么对一个 $i$，其中的 $b_i$ 和 $a_1+\cdots +a_i$ 就是固定的，我们需要快速确定 $j$，使得上式最大。

我们可以预处理 $a$ 的前缀和 $s_i=a_1+a_2+\cdots +a_i$。上式转化为 $s_{j-1}+b_j-s_i+b_i$，其实我们只需要知道 $[i+1,i+tn-1]$ 中 $s_{j-1}+b_j$ 最大值即可。

可以用单调队列动态维护区间最大值。就是滑动窗口问题。或者可以用 $set$，时间慢一点，但是不影响。

code1：

拓扑排序

#include <iostream>
#include <cstdio>
#include <vector>
#include <set>
#include <queue>
using namespace std;
const int maxn=5e5+5;
#define pii pair<int,int>
const int inf=1e9;int n,ans=0;
set<int> g[maxn];
int clean[maxn];vector<int> ring;
set<int> S;
int to[maxn],twin[maxn];//向环外走可以走到多少1点 以它为中转点向外走两条叉的1点数 
void topu(){//拓扑排序找环，并找到环上点向环外可以走到多少1点 queue<int> q;for(int u=1;u<=n;u++)if(g[u].size()==1)q.push(u);while(!q.empty()){int u=q.front();q.pop();for(auto v:g[u]){g[v].erase(u);twin[v]=max(twin[v],to[v]+to[u]);ans=max(ans,twin[v]);to[v]=max(to[v],clean[v]+to[u]);if(g[v].size()==1)q.push(v);}g[u].clear();}//	for(int u=1;u<=n;u++){
//		cout<<u<<":";
//		for(auto v:g[u])
//			cout<<v<<" ";
//		cout<<endl;
//	}for(int u=1;u<=n;u++)if(g[u].size()>0)S.insert(u);for(int u=*S.begin(),fa=*g[u].begin();;){ring.push_back(u);for(auto v:g[u]){if(v==fa)continue;if(v==ring[0])return;fa=u;u=v;break;}}
}int main(){cin>>n;for(int i=1;i<=n;i++)cin>>clean[i],to[i]=clean[i];for(int i=1,u,v;i<=n;i++){cin>>u>>v;g[u].insert(v);g[v].insert(u);}topu();int tn=ring.size();vector<int> a(tn*2+5),b(tn*2+5),s(tn*2+5);for(int i=1;i<=tn;i++){a[i]=a[i+tn]=clean[ring[i-1]];b[i]=b[i+tn]=to[ring[i-1]];}for(int i=1;i<=tn*2;i++)s[i]=s[i-1]+a[i];deque<pii> dq;//下标 值 for(int j=1;j<tn;j++){int val=s[j-1]+b[j];while(!dq.empty() && dq.back().second<=val)dq.pop_back();dq.push_back(pii(j,val));}for(int i=1,j=tn,val;i<=tn;i++,j++){//i为左端点，j为右端点 while(!dq.empty() && dq.front().first<=i)dq.pop_front();val=s[j-1]+b[j];while(!dq.empty() && dq.back().second<=val)dq.pop_back();dq.push_back(pii(j,val));int max_val=dq.front().second-s[i]+b[i];ans=max(ans,max_val);}for(auto u:ring){ans=max(ans,twin[u]+s[tn]-clean[u]);}cout<<ans<<endl;return 0;
}
/*
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*/

code2：

$dfs$

#include <iostream>
#include <cstdio>
#include <vector>
#include <set>
#include <queue>
#include <algorithm>
#include <ctime>
using namespace std;
const int maxn=5e5+5;
const int inf=1e9;
#define pii pair<int,int>
//#define int long longint n,ans=0;
set<int> g[maxn];int clean[maxn];
int to[maxn];//向环外走可以走到多少1点 vector<int> cir;
bool incir[maxn];vector<int> stk;
bool vis[maxn];
bool find_cir(int u,int fa){
//	cout<<u<<' '<<fa<<endl;vis[u]=true;stk.push_back(u);for(auto v:g[u]){if(fa==v)continue;if(vis[v]){while(true){int t=stk.back();stk.pop_back();incir[t]=true;cir.push_back(t);if(t==v)break;}return true;}if(find_cir(v,u))return true;}stk.pop_back();vis[u]=false;return false;
}void dfs(int u,int fa){for(auto v:g[u]){if(incir[v] || fa==v)continue;dfs(v,u);ans=max(ans,to[v]+to[u]);to[u]=max(to[u],to[v]+clean[u]);}
}signed main(){cin>>n;for(int i=1;i<=n;i++)cin>>clean[i],to[i]=clean[i];for(int i=1,u,v;i<=n;i++){cin>>u>>v;g[u].insert(v);g[v].insert(u);}find_cir(1,-1);for(auto u:cir)dfs(u,-1);int tn=cir.size();vector<int> a(tn*2+5),b(tn*2+5),s(tn*2+5);for(int i=1;i<=tn;i++){a[i]=a[i+tn]=clean[cir[i-1]];b[i]=b[i+tn]=to[cir[i-1]];}for(int i=1;i<=tn*2;i++)s[i]=s[i-1]+a[i];set<pii> S;for(int j=1;j<tn;j++){int val=s[j-1]+b[j];S.insert(pii(val,j));}for(int i=1,j=tn,val;i<=tn;i++,j++){//i为左端点，j为右端点 val=s[j-1]+b[j];S.insert(pii(val,j));while(!S.empty() && (*S.rbegin()).second<=i)S.erase(*S.rbegin());int max_val=(*S.rbegin()).first-s[i]+b[i];ans=max(ans,max_val);}int cnt=s[tn];//环上所有1点和 
//	cout<<cnt<<endl;for(auto u:cir){int mx1=-inf,mx2=-inf;for(auto v:g[u]){if(incir[v])continue;if(to[v]>mx1){mx2=mx1;mx1=to[v];}else if(to[v]>mx2){mx2=to[v];}}
//		cout<<"***"<<u<<" "<<mx1<<" "<<mx2<<endl;ans=max(ans,cnt+mx1+mx2);}cout<<ans<<endl;return 0;
}
/*
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*/