F. Gift
基环树处理环。
给一棵基环树，要求删掉一条边后还是一棵树，说明只能删掉这棵基环树上的环上的边。
删掉边后还要保证以 \(p\) 作为根节点时，其他节点的儿子数量不超过 \(3\)，说明根节点的度数一定是小于等于 \(3\) 的，除此之外，如果树上存在度数大于 \(4\) 的点，那么无论如何都无法满足该要求。
所以我们可以总体维护度数小于 \(4\) 的、等于 \(4\) 的、大于 \(4\) 的，然后枚举环上的边，看删掉之后是否还存在度数大于 \(4\) 的点，有就跳过，否则加上度数小于 \(4\) 的个数。
点击查看代码
#include <bits/stdc++.h>using namespace std;using i64 = long long;int main() {ios::sync_with_stdio(false);cin.tie(nullptr);int n;cin >> n;vector<int> in(n + 1);vector e(n + 1, vector<int>());for (int i = 1; i <= n; i += 1) {int u, v;cin >> u >> v;e[u].push_back(v);e[v].push_back(u);in[u] += 1, in[v] += 1;}int idx = 0;bool found = false;vector<int> loop,dfn(n + 1, 0), fa(n + 1, 0);function<void(int)> dfs = [&](int u) {dfn[u] = ++idx;for (int v : e[u]) {if (v == fa[u]) {continue;}if (!dfn[v]) {fa[v] = u;dfs(v);if (found) {return;}}else if (dfn[v] < dfn[u]) {int cur = u;while (cur != v) {loop.push_back(cur);cur = fa[cur];}loop.push_back(v);found = true;return;}}};dfs(1);i64 ans = 0;int cnt[3] {};auto update = [&](int x, int v)->void{if (in[x] > 4) {cnt[2] += v;}else if (in[x] > 3) {cnt[1] += v;}else { cnt[0] += v; }};for (int i = 1; i <= n; i += 1) {update(i, 1);}int m = loop.size();for (int i = 0; i < m; i += 1) {int x = loop[i], y = loop[(i + 1) % m];update(x, -1), update(y, -1);in[x] -= 1, in[y] -= 1;update(x, 1), update(y, 1);if (!cnt[2]) {ans += cnt[0];}update(x, -1), update(y, -1);in[x] += 1, in[y] += 1;update(x, 1), update(y, 1);}cout << ans << "\n";return 0;
}