比赛链接
AB
简单模拟即可，注意审清题意，手模小样例。
C
想复杂了，用链表实现的，但实际上只需要维护一个栈就可以了，每加进来一个数就看一下栈顶的 4 个。
D
这种式子考虑将某一个变量的选择变成某一个东西的最优化问题，然后去维护这个东西。
比如这里我们枚举 \(x\)，然后维护 \(C_i - B_i\) 的最大值，这样我们选择一个 y 就等效为把后面的 \(B\) 全部加上，然后选一个最大的 \(C_i - B_i\)。
E
考虑到这个结构是基环树森林，我们可以考虑从这个视角来做。
建出来一颗基环树后，我们分别处理从一个点跳到环上（或者跳不到环上）和在环上跳多少次。
在树上跳到部分用倍增实现，环的部分我是先存下来环上的点，破环成链后维护前缀和。
当然如果你聪明一点，发现可以直接倍增做（大雾。
F
我们最初想法是，统计 \(\text{mex} = x\) 的路径条数 \(f(x)\)，但这不好做，很难计算包含 0 到 \(x - 1\) 但不包含 \(x\) 的方案数。
trick 是，如果我计算 \(\text{mex} \geq x\) 的路径条数 \(g(i)\)。那么原本的答案是 \(\sum f(i) \times i\) 和 \(\sum g(i)\) 是等价的。
写法上需要注意一些细节，比如如果你往上跳碰到的第一个在路径上的数是 0，要把 siz[0] 减去你所在这个子树的大小。
代码
#include <bits/stdc++.h>
using namespace std;namespace mlyy {#define int long longconst int N = 2e5 + 100;int n;vector<int> edge[N];int siz[N];int dfn[N];int f[N];int idx;int ans;void dfs(int u, int fa) {siz[u] = 1;f[u] = fa;dfn[u] = ++idx;for (int v : edge[u]) {if (v == fa) continue;dfs(v, u);siz[u] += siz[v];if (u == 0) {ans -= siz[v] * (siz[v] + 1) / 2;}}}int vis[N];void main() {cin >> n;for (int i = 1;i < n;i++) {int u, v;cin >> u >> v;edge[u].push_back(v);edge[v].push_back(u);}ans = n * (n + 1) / 2;dfs(0, -1);int x = 0, y = 0;int lst = 0;vis[0] = 1;// cout << ans << '\n';for (int i = 1;i < n;i++) {// cout << i << " " << ans << "\n";if (vis[i]) {ans += lst;continue;}int u = -1, v = -1;for (u = i;;u = f[u]) {// cout << u << " " << vis[u] << "\n";if (vis[u] == 1) break;vis[u] = 1;v = u;}if (u == x) x = i;else if (u == y) y = i;else break;// cout << v << "?\n";// cout << i << ":";// cout << x << ' ' << y << ": " << siz[y] - siz[v] << " " << siz[x] << "\n";if (u == 0) siz[0] -= siz[v];ans += (lst = siz[x] * siz[y]);//, cout << siz[x] * siz[y] << "\n";}cout << ans;}
}signed main() {mlyy::main();return 0;
}