洛谷上七级和八级的题还没有，等有了再写，先写一下六级的吧。
今年这个六级题有点简单了，全是非常经典非常板的题目，基本看一眼就秒了，下面我来讲一下我的思路，洛谷已经有六级题目测试数据了，我已经测过了，写了的可以去测测哦。
P11963 [GESP202503 六级] 环线
原题链接：P11963 [GESP202503 六级] 环线 - 洛谷
题目描述
小 A 喜欢坐地铁。地铁环线有 n 个车站，依次以 1,2,⋯,n 标号。车站 i (1≤i<n) 的下一个车站是车站 i+1。特殊地，车站 n 的下一个车站是车站 1。
小 A 会从某个车站出发，乘坐地铁环线到某个车站结束行程，这意味着小 A 至少会经过一个车站。小 A 不会经过一个车站多次。当小 A 乘坐地铁环线经过车站 i 时，小 A 会获得 ai 点快乐值。请你安排小 A 的行程，选择出发车站与结束车站，使得获得的快乐值总和最大。
输入格式
第一行，一个正整数 n，表示车站的数量。
第二行，n 个整数 ai，分别表示经过每个车站时获得的快乐值。
输出格式
一行，一个整数，表示小 A 能获得的最大快乐值。
输入输出样例
输入 #1
4 -1 2 3 0
输出 #1
5
输入 #2
5 -3 4 -5 1 3
输出 #2
5
说明/提示
对于 20% 的测试点，保证 1≤n≤200。
对于 40% 的测试点，保证 1≤n≤2000。
对于所有测试点，保证 1≤n≤2×10^5，−10^9≤ai≤10^9。
解题思路：
解法1：分类讨论+前缀最小
这个题目其实就是有一个环形数组，要你找一个连续的段，这个连续的段中元素的和要最大，并且这个段中至少要有一个元素(也就是非空)，仔细想想可以发现实际上只有俩种情况，如下图所示：
第1种其实就是中间的某一个连续段。
又由于是环形的，所以实际上就有了我们的情况2。
现在我们知道了一共就这两种情况，那么分别计算即可。
对于情况1：实际上就是找一个和最大的连续子段，为了方便描述不妨设原数组前缀和为s，假设我们的连续段是[l，r]，那么用前缀和数组表示就是s[r] - s[l -1]，我们可以固定其中一个的大小，我们可以从小到大枚举r, 那么我们的s[r]就固定了，要使得表达式s[r] - s[l - 1]最大，那么只需要使s[l -1]最小即可，由于l的范围是[0, 1, 2, ... r - 1]，可以发现其实就是s数组的一个前缀最小，所以我们对s数组记录一个前缀最小即可。
对于情况2：选中头部一个红色段和尾部一个红色段，直接枚举这两个红色段的位置可以发现时间复杂度是O(n^2)的，n比较大，会超时，所以不能直接枚举，我们考虑优化，根据情况1的处理方式其实可以发现，虽然红色段不好处理，但是中间的蓝色段实际上就对应到了情况1，只不过情况1求的是和最大，这里对于蓝色段求一个和最小的段即可，处理方式是一样的，然后所有数的和减去蓝色段其实就是两个红色段了呀。
对于上述两种情况取一个最大值就是答案了。
时间复杂度：O(n), 所有处理都是线性的。
空间复杂度：O(n)
解法二：滑动串口+区间最小
对于环形问题，比较常见的处理方式就是破环成链，这里也可以这样处理，不妨设a数组原来的长度是n，把原数组a复制一遍放到a的末尾，现在我们的a数组的长度变为了n * 2，那么现在就可以把我们的环形问题转变成线性的了，现在实际上就是维护一个长为n的滑动串口，在这个滑动窗口求和最大的连续子段的和，那么接下来就和解法1中的情况1比较类似了，由于我们需要维护一段连续的前缀的最小值，同时需要动态添加某个前缀和和动态删除某个前缀和，我们需要一个能够排序的数据结构，所以我们可以使用map进行维护，这里我们每次需要右窗口往右边移动1次，同时需要考虑左窗口是否需要右移，当右窗口到达位置n + 1时，我们的窗口大小就是n + 1了，所以我们的左窗口需要右移一个位置，同时把对应的前缀和从map中减去，处理完当前位置之后，需要把当前位置的前缀和值加入map，直到我们的右窗口到了最后一个位置(n * 2这个位置)，我们所有的大小为n的滑动窗口就处理完了，对于每一种窗口的情况取一个最大值就是答案了。
时间复杂度：需要一个map来维护大小为n的滑动窗口，所以时间复杂度为O(nlog(n))。
空间复杂度：O(n)。
解法1代码就不放了，可以自己去实现一下
解法2cpp代码如下：
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <map>
#include <set>
#include <queue>
#include <vector>
#include <cmath>using namespace std;
typedef long long LL;
typedef pair<int, int> PII;
const int N = 2e5 + 10, mod = 1e9 + 7;
int n, m, k;int a[N * 2];
LL s[N * 2];
void solve()
{cin >> n;for (int i = 1; i <= n; i++)cin >> a[i], a[i + n] = a[i];for (int i = 1; i <= n * 2; i++)s[i] = s[i - 1] + a[i];LL ans = -1e18;map<LL, int> mp;mp[0]++;for (int i = 1; i <= n * 2; i++){if (i > n){mp[s[i - n - 1]]--;if (mp[s[i - n - 1]] == 0)mp.erase(s[i - n - 1]);}ans = max(ans, s[i] - mp.begin()->first);mp[s[i]]++;}cout << ans << '\n';
}
int main()
{ios::sync_with_stdio(false);cin.tie(0), cout.tie(0);int T = 1;while (T--){solve();}return 0;
}P11962 [GESP202503 六级] 树上漫步
题目描述
小 A 有一棵 n 个结点的树，这些结点依次以 1,2,⋯,n 标号。
小 A 想在这棵树上漫步。具体来说，小 A 会从树上的某个结点出发，每⼀步可以移动到与当前结点相邻的结点，并且小 A 只会在偶数步（可以是零步）后结束漫步。
现在小 A 想知道，对于树上的每个结点，从这个结点出发开始漫步，经过偶数步能结束漫步的结点有多少个（可以经过重复的节点）。
输入格式
第一行，一个正整数 n。
接下来 n−1 行，每行两个整数 ui,vi，表示树上有⼀条连接结点 ui 和结点 vi 的边。
输出格式
一行，n 个整数。第 i 个整数表示从结点 i 出发开始漫步，能结束漫步的结点数量。
输入输出样例
输入 #1复制
3 1 3 2 3
输出 #1复制
2 2 1
输入 #2复制
4 1 3 3 2 4 3
输出 #2复制
3 3 1 3
说明/提示
对于 40% 的测试点，保证 1≤n≤10^3。
对于所有测试点，保证 1≤n≤2×10^5。
解题思路：
非常经典的换根dp了，首先最简单的做法肯定就是枚举起点，然后依次计算，枚举起点时间为O(n)，同时计算需要走遍整棵树，时间为O(n)，那么时间复杂度就是O(n^2)，n比较大，这样会超时，所以不能直接暴力枚举起点，我们可以先以1号点为起点，然后计算从1号点出发经过偶数步可以到达的点的数量，和经过奇数步可以到达的点，我们不妨设f[i][0]表示从i号点经过偶数步可以到达的点的数量，f[i][1]表示从i号点经过奇数步可以到达的点的数量，那么有人会问题目不是只需要我们求偶数步的吗？这里为啥要求奇数步的呀？别急.......，等一下会说，我们来看一下这个图：
如上图所示：我们通过这个来求1号点经过偶数步可以到达的点，由于1号点到2号点经过了1步，那么到1号点偶数步，实际上就是到2号点奇数步，所以现在你知道了为什么还要计算奇数的了吧，那么对于1号点的计算公式为f[1][0] = f[2][1] + f[3][1]，f[1][1] = f[2][0] + f[3][0]，那么对于其他点同理，不过我们肯定要从叶子往根计算，所以先往下递归，然后计算当前结点对应的值。
1号点的计算完了，然后肯定就是需要计算其他点的了，我们考虑换根操作，我们来看换根操作会产生什么影响吧， 1号换到2号，此时f[2][0]和f[2][1]对应的是以2号结点为子树的对应部分，此时以2号点为起点了，那么就需要加上2号结点往上的部分了，那么到2号结点偶数步的点要加上到1号结点奇数步的点这一部分，由于到1号结点奇数步的结点包含到了以2号结点为子树那一部分，所以还要把那一部分减去(减去重复计算)，那么计算公式如下：
(1)f[2][0] += f[1][1] - f[2][0];
(2)f[2][1] += f[1][0] - f[2][1];
对于其他的点进行换根的操作产生的影响和这里是一样的，进行同样的处理即可。
这里就是先计算再递归了。
时间复杂度：O(n)。
空间复杂度：O(n)。
cpp代码如下：
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <map>
#include <set>
#include <queue>
#include <vector>
#include <cmath>using namespace std;
typedef long long LL;
typedef pair<int, int> PII;
const int N = 2e5 + 10, mod = 1e9 + 7;
int n, m, k;vector<int> g[N];
int f[N][2];void dfs1(int u, int fa)
{f[u][0] = 1;for (auto &v : g[u]){if (v == fa)continue;dfs1(v, u);f[u][0] += f[v][1];f[u][1] += f[v][0];}
}void dfs2(int u, int fa)
{for (auto &v : g[u]){if (v == fa)continue;f[v][0] += f[u][1] - f[v][0];f[v][1] += f[u][0] - f[v][1];dfs2(v, u);}
}
void solve()
{cin >> n;for (int i = 1; i < n; i++){int u, v;cin >> u >> v;g[u].push_back(v);g[v].push_back(u);}dfs1(1, -1);dfs2(1, -1);for (int i = 1; i <= n; i++)cout << f[i][0] << ' ';cout << '\n';
}
int main()
{ios::sync_with_stdio(false);cin.tie(0), cout.tie(0);int T = 1;while (T--){solve();}return 0;
}
