【题解】2025 蓝桥杯国赛 CA
本文最后更新于：2025年6月21日 凌晨
E. 树
令 \(dp[x][0/1/2]\) 表示在以 \(x\) 为根的子树中，不同选取情况对应的方案数。
- \(dp[x][0]\)：节点 \(x\) 被选中。
- \(dp[x][1]\)：节点 \(x\) 未被选中，但其恰好一个儿子被选中。
- \(dp[x][2]\)：节点 \(x\) 未被选中，且其所有儿子也未被选中。
转移如下
\[ \large dp[x][0]=\prod_{y\in son[x]}dp[y][2] \]
\[ \large dp[x][1]=\sum_{y\in son[x]}\left(dp[y][0]\prod_{z\in son[x],z\neq y}\left(dp[z][1]+dp[z][2]\right)\right) \]
\[ \large dp[x][2]=\prod_{y\in son[x]}(dp[y][1]+dp[y][2]) \]
答案是 \(dp[1][0]+dp[1][1]+dp[1][2]-1\)，减一是为了减去空集。
时间复杂度 \(O(n)\)。
Code
#include <bits/stdc++.h>
using namespace std;
#define fre(x) freopen(#x".in", "r", stdin); freopen(#x".out", "w", stdout)
#define ck(x) { cout << "check " << x << endl;}
#define int long long
#define double long double
#define inf 0x3fffffffffffffff
//-------------- templates above --------------
constexpr int mod = 998244353;
int qpow(int k, int n) {
int s = 1;
for ( ; n; n >>= 1, k = k * k % mod) {
if (n & 1) s = s * k % mod;
}
return s;
}
void solve() {
int n;
cin >> n;
vector<vector<int>> adj(n + 1);
for (int i = 1; i < n; i++) {
int x, y;
cin >> x >> y;
adj[x].push_back(y);
adj[y].push_back(x);
}
vector<array<int, 3>> dp(n + 1);
auto dfs = [&] (auto self, int x, int fa) -> void {
if (x != 1 && adj[x].size() == 1) {
dp[x][0] = 1;
dp[x][1] = 0;
dp[x][2] = 1;
return ;
}
int s0 = 1;
int s1 = 1;
for (auto y : adj[x]) {
if (y == fa) {
continue;
}
self(self, y, x);
s0 = s0 * dp[y][2] % mod;
s1 = s1 * (dp[y][1] + dp[y][2]) % mod;
}
dp[x][0] = s0;
dp[x][2] = s1;
for (auto y : adj[x]) {
if (y == fa) {
continue;
}
int inv = qpow(dp[y][1] + dp[y][2], mod - 2);
dp[x][1] = (dp[x][1] + dp[y][0] * s1 % mod * inv % mod) % mod;
}
};
dfs(dfs, 1, 0);
int ans = (dp[1][0] + dp[1][1] + dp[1][2] - 1 + mod) % mod;
cout << ans << "\n";
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int T = 1;
while (T--) {
solve();
}
return 0;
}F. 连锁反应
暴力做法就是对于两个炸弹 \(x, y\)，如果 \(x\) 炸了能顺带把 \(y\) 炸了，就连一条 \(x\to y\)。
将这张图缩点，得到一个 DAG，此时只用数有多少个点入度为 \(0\) 即可（我们可以从这些点开始引爆）。
注意到对于每个炸弹，能被它连锁引爆的炸弹形成一个区间，我们可以二分找到这个区间，从该点向这个区间连边，也就是线段树优化建图。具体的，从这个炸弹对应的叶节点向线段树上被这个区间包含的 \(O(\log n)\) 个节点连边。
问题就在，线段树结构边的存在，使得缩点后我们不能单纯地找入度为 \(0\) 的点了。
但我们仍然可以构建出炸弹的传递链：从所有包含炸弹的 SCC 出发 BFS，标记可达的点。而没被这些点指向的包含炸弹的 SCC，就是一个可行的引爆点。
时间复杂度 \(O(n\log n)\)。
Code
#include <bits/stdc++.h>
using namespace std;
#define fre(x) freopen(#x".in", "r", stdin); freopen(#x".out", "w", stdout)
#define ck(x) { cout << "check " << x << endl;}
#define double long double
#define inf 0x3fffffff
struct SegEdge {
int n, all;
vector<vector<int>> adj;
vector<int> id;
SegEdge() {}
SegEdge(int n) {
this->n = n;
all = 4 * n;
adj.resize(all + 1);
id.resize(n + 1);
build(1, 1, n);
}
void build(int p, int l, int r) {
if (l == r) return id[l] = p, void();
adj[p].push_back(p << 1);
adj[p].push_back(p << 1 | 1);
int mid = l + r >> 1;
build(p << 1, l, mid);
build(p << 1 | 1, mid + 1, r);
}
void addEdge(int p, int l, int r, int lx, int rx, int x) {
if (lx <= l && r <= rx) {
adj[x].push_back(p);
return ;
}
int mid = l + r >> 1;
if (lx <= mid) addEdge(p << 1, l, mid, lx, rx, x);
if (rx > mid) addEdge(p << 1 | 1, mid + 1, r, lx, rx, x);
}
void PtoS(int x, int l, int r) {
addEdge(1, 1, n, l, r, id[x]);
}
};
//-------------- templates above --------------
void solve() {
int n;
cin >> n;
vector<array<int, 3>> a(n + 1);
for (int i = 1; i <= n; i++) {
int p, l, r;
cin >> p >> l >> r;
a[i] = {p, l, r};
}
sort(a.begin() + 1, a.end());
vector<int> b(n + 1);
for (int i = 1; i <= n; i++) {
b[i] = a[i][0];
}
SegEdge seg(n);
for (int i = 1; i <= n; i++) {
auto [p, l, r] = a[i];
int L = lower_bound(b.begin(), b.end(), p - l) - b.begin();
int R = upper_bound(b.begin(), b.end(), p + r) - b.begin() - 1;
if (L < R) {
seg.PtoS(i, L, R);
}
}
const int N = seg.all;
vector<int> dfn(N + 1), low(N + 1), stk(N + 1), c(N + 1);
vector<bool> vis(N + 1);
int tim = 0, top = 0, cnt = 0;
auto tarjan = [&] (auto self, int x) -> void {
dfn[x] = low[x] = ++tim;
vis[x] = true;
stk[++top] = x;
for (auto y : seg.adj[x]) {
if (!dfn[y]) {
self(self, y);
low[x] = min(low[x], low[y]);
} else if (vis[y]) {
low[x] = min(low[x], dfn[y]);
}
}
if (dfn[x] == low[x]) {
int now; ++cnt;
do {
now = stk[top--];
vis[now] = false;
c[now] = cnt;
} while(x != now);
}
};
for (int i = 1; i <= N; i++) {
if (!dfn[i]) {
tarjan(tarjan, i);
}
}
vector<vector<int>> Adj(cnt + 1);
vector<array<int, 2>> s;
for (int x = 1; x <= N; x++) {
for (auto y : seg.adj[x]) {
if (c[x] != c[y]) {
s.push_back({c[x], c[y]});
Adj[c[x]].push_back(c[y]);
}
}
}
vector<int> act(cnt + 1), reach(cnt + 1);
queue<int> q;
for (int i = 1; i <= n; i++) {
int x = c[seg.id[i]];
act[x] = true;
reach[x] = true;
q.push(x);
}
while (!q.empty()) {
int x = q.front();
q.pop();
for (auto y : Adj[x]) {
if (!reach[y]) {
reach[y] = true;
q.push(y);
}
}
}
vector<int> deg(cnt + 1);
for (auto [x, y] : s) {
if (reach[x]) {
deg[y]++;
}
}
int ans = 0;
for (int i = 1; i <= cnt; i++) {
if (act[i] && deg[i] == 0) {
ans++;
}
}
cout << ans << "\n";
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int T = 1;
while (T--) {
solve();
}
return 0;
}G. 翻转硬币
下标按\(\bmod \text{LCM}(1,2,3)=6\) 分组，每组建一棵线段树。
第一种操作要么对\(\bmod 0,2,4\) 对应的三棵线段树操作，要么对\(\bmod 1, 3, 5\) 对应的三棵线段树操作。
第二种操作，同理每次对两棵线段树操作。
第三种操作，对所有线段树操作。
对于每一棵线段树，维护懒标记 \(\text{rev}\) 表示是否翻转，再维护一个区间和即可。
容易错的地方是怎么把区间 \([l,r]\) 映射到某棵线段树上对应的区间 \([L,R]\) 找到，比较稳妥的方式是二分。
时间复杂度 \(O((n+m)\log n)\)。
Code
#include <bits/stdc++.h>
using namespace std;
#define fre(x) freopen(#x".in", "r", stdin); freopen(#x".out", "w", stdout)
#define ck(x) { cout << "check " << x << endl;}
#define int long long
#define double long double
#define inf 0x3fffffffffffffff
template<class Info, class Tag>
struct LazySegmentTree {
int n;
vector<Info> tr;
vector<Tag> tag;
LazySegmentTree() {}
LazySegmentTree(vector<Info> &a) {
init(a);
}
void init(vector<Info> &a) {
n = a.size() - 1;
const int N = (4 << __lg(n + 1)) + 5;
tr.assign(N, Info());
tag.assign(N, Tag());
build(1, 1, n, a);
}
#define ls (p << 1)
#define rs (p << 1 | 1)
void build(int p, int l, int r, vector<Info> &a) {
if (l == r) {
tr[p] = a[l];
return ;
}
int m = l + r >> 1;
build(ls, l, m, a);
build(rs, m + 1, r, a);
pushup(p);
}
void pushup(int p) {
tr[p] = tr[ls] + tr[rs];
}
void apply(int p, const Tag &x) {
tr[p].apply(x);
tag[p].apply(x);
}
void pushdown(int p) {
apply(ls, tag[p]);
apply(rs, tag[p]);
tag[p] = Tag();
}
Info query(int p, int l, int r, int ql, int qr) {
if (ql <= l && qr >= r) {
return tr[p];
}
int m = l + r >> 1;
pushdown(p);
if (qr <= m) {
return query(ls, l, m, ql, qr);
} else if (ql >= m + 1) {
return query(rs, m + 1, r, ql, qr);
} else {
return query(ls, l, m, ql, qr) + query(rs, m + 1, r, ql, qr);
}
}
Info query(int ql, int qr) {
if (ql > qr) {
return Info();
}
return query(1, 1, n, ql, qr);
}
void modify(int p, int l, int r, int ql, int qr, const Tag &x) {
if (l > qr || r < ql) {
return ;
}
if (ql <= l && qr >= r) {
apply(p, x);
return ;
}
pushdown(p);
int m = l + r >> 1;
modify(ls, l, m, ql, qr, x);
modify(rs, m + 1, r, ql, qr, x);
pushup(p);
}
void modify(int ql, int qr, const Tag &x) {
if (ql > qr) {
return ;
}
return modify(1, 1, n, ql, qr, x);
}
};
struct Tag {
int rev = 0;
Tag() {}
Tag(int A) {
rev = A;
}
void apply(const Tag &t) & {
rev ^= t.rev;
}
};
struct Info {
int sum = 0;
int l = 0;
int r = 0;
Info() {}
Info(int A, int B) {
sum = A;
l = r = B;
}
void apply(const Tag &t) & {
if (t.rev) {
sum = (r - l + 1) - sum;
}
}
};
Info operator+(const Info &a, const Info &b) {
Info c;
c.sum = a.sum + b.sum;
c.l = min(a.l, b.l);
c.r = max(a.r, b.r);
return c;
}
//-------------- templates above --------------
void solve() {
int n, m;
cin >> n >> m;
vector<vector<int>> pos(6, {0});
vector<vector<Info>> a(6, {{0, 0}});
vector<int> tot(6);
for (int i = 1; i <= n; i++) {
int x;
cin >> x;
pos[i % 6].push_back(i);
a[i % 6].push_back({x, ++tot[i % 6]});
}
vector<LazySegmentTree<Info, Tag>> seg(6);
for (int i = 0; i < 6; i++) {
if (a[i].size() > 1) {
seg[i].init(a[i]);
}
}
auto get = [&] (int i, int l, int r) -> array<int, 2> {
int L = lower_bound(pos[i].begin(), pos[i].end(), l) - pos[i].begin();
int R = upper_bound(pos[i].begin(), pos[i].end(), r) - pos[i].begin() - 1;
return {L, R};
};
while (m--) {
int op, l, r;
cin >> op >> l >> r;
if (op == 1) {
for (int i = l % 6, j = 0; j < 3; i = (i + 2) % 6, j++) {
if (a[i].size() > 1) {
auto [L, R] = get(i, l, r);
seg[i].modify(L, R, {1});
}
}
} else if (op == 2) {
for (int i = l % 6, j = 0; j < 2; i = (i + 3) % 6, j++) {
if (a[i].size() > 1) {
auto [L, R] = get(i, l, r);
seg[i].modify(L, R, {1});
}
}
} else if (op == 3) {
for (int i = 0; i < 6; i++) {
if (a[i].size() > 1) {
auto [L, R] = get(i, l, r);
seg[i].modify(L, R, {1});
}
}
} else {
int ans = 0;
for (int i = 0; i < 6; i++) {
if (a[i].size() > 1) {
auto [L, R] = get(i, l, r);
ans += seg[i].query(L, R).sum;
}
}
cout << ans << "\n";
}
}
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int T = 1;
while (T--) {
solve();
}
return 0;
}H. 斐波那契数列
纸上展开几项易得： \[ \large G_n=G_1^{F_{n-2}}G_2^{F_{n-1}}(n\ge 3) \] 令 \(H_n=\prod\limits_{i=1}^{n}G_i\)，\(S_n=\sum\limits_{i=1}^{n}F_i\)，纸上画一下也有 \[ \large H_n=G_1^{S_{n-2}+1}G_2^{S_{n-1}}(n\ge 3) \] 斐波那契数列有性质 \[ \large S_n=F_{n+2}-1 \] 和 \(G_1=2,G_2=3\) 一起代入，得 \[ \large H_n=2^{F_n}\cdot3^{F_{n+1}-1} \] 令 \(p=998244353\)，由欧拉定理，我们相当于求 \[ \large 2^{F_n\bmod (p-1)}\cdot 3^{F_{n+1}-1\bmod (p-1)}\bmod p \] 至于求 \(F_n\)，用一个经典的递推 \[ \begin{pmatrix} F_n \\ F_{n-1} \end{pmatrix} = \begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix} \begin{pmatrix} F_{n-1} \\ F_{n-2} \end{pmatrix} \] 也就是 \[ \begin{pmatrix} F_n \\ F_{n-1} \end{pmatrix} = \begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix}^{n-2} \begin{pmatrix} F_{2} \\ F_{1} \end{pmatrix} \] 在 \(\bmod (p-1)\) 下矩阵快速幂即可。
时间复杂度 \(O(2^3\log n+\log p)\)。
Code
#include <bits/stdc++.h>
using namespace std;
#define fre(x) freopen(#x".in", "r", stdin); freopen(#x".out", "w", stdout)
#define ck(x) { cout << "check " << x << endl;}
#define int long long
#define double long double
#define inf 0x3fffffffffffffff
struct matrix {
int n, m;
vector<vector<int>> a;
matrix(int n) : n(n), m(n), a(n, vector<int>(n, 0)) {}
matrix(int n, int m) : n(n), m(m), a(n, vector<int>(m, 0)) {}
matrix(int n, int m, int k) : n(n), m(m), a(n, vector<int>(m, k)) {}
void read() {
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
cin >> a[i][j];
}
}
}
void print() {
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
cout << a[i][j] << " \n"[j == m - 1];
}
}
}
void build() {
for (int i = 0; i < min(n, m); i++) {
a[i][i] = 1;
}
}
matrix tp() {
matrix z(m, n);
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
z.a[j][i] = a[i][j];
}
}
return z;
}
};
constexpr int modp = 998244352;
matrix operator * (const matrix &x, const matrix &y) {
assert(x.m == y.n);
matrix z(x.n, y.m);
for (int k = 0; k < x.m; k++) {
for (int i = 0; i < x.n; i++) {
for (int j = 0; j < y.m; j++) {
z.a[i][j] += x.a[i][k] * y.a[k][j] % modp;
z.a[i][j] %= modp;
}
}
}
return z;
}
matrix qpow(matrix a, int k) {
assert(a.n == a.m);
matrix z(a.n);
z.build();
for ( ; k; k >>= 1, a = a * a) {
if (k & 1) z = z * a;
}
return z;
}
constexpr int mod = 998244353;
int qpow(int k, int n) {
int s = 1;
for ( ; n; n >>= 1, k = k * k % mod) {
if (n & 1) s = s * k % mod;
}
return s;
}
//-------------- templates above --------------
void solve() {
int n;
cin >> n;
matrix A(2, 2);
A.a[0][0] = 1;
A.a[0][1] = 1;
A.a[1][0] = 1;
matrix S(2, 1);
S.a[0][0] = 1;
S.a[1][0] = 1;
auto T = qpow(A, n - 1) * S;
int p = T.a[1][0];
int q = (T.a[0][0] - 1 + modp) % modp;
int ans = qpow(2, p) * qpow(3, q) % mod;
cout << ans << "\n";
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int T = 1;
while (T--) {
solve();
}
return 0;
}I. 游戏
结论：答案至多为 \(2\)。
考虑如下构造：
- 先连一条 \((n-2,n)\)，此时你可以将位于 \(n-1\) 和 \(n-2\) 上的数进行交换。
- 再连一条 \((1,n)\)，这样你就可以循环位移了。
那能循环位移，你每次就可以把要交换的两个相邻的数移到最后进行交换。
也就是说，你可以自由交换相邻的数了，也就一定能排序，得证。
接下来考虑什么时候答案为 \(0\) 或 \(1\)。
- 一开始就排好序就是 \(0\)。
- 若能通过至多一次区间循环位移排好序就是 \(1\)。
- 否则就是 \(2\)。
Code
#include <bits/stdc++.h>
using namespace std;
#define fre(x) freopen(#x".in", "r", stdin); freopen(#x".out", "w", stdout)
#define ck(x) { cout << "check " << x << endl;}
#define int long long
#define double long double
#define inf 0x3fffffffffffffff
//-------------- templates above --------------
void solve() {
int n;
cin >> n;
vector<int> a(n);
for (int i = 1; i < n; i++) {
cin >> a[i];
}
if (is_sorted(a.begin(), a.end())) {
cout << 0 << "\n";
return ;
}
int l = 1, r = n - 1;
while (a[l] == l) {
l++;
}
while (a[r] == r) {
r--;
}
int p = min_element(a.begin() + l, a.begin() + r + 1) - a.begin();
for (int i = p + 1, lst = p; i != p; i++) {
if (i == r + 1) {
i = l;
}
if (a[i] != a[lst] + 1) {
cout << 2 << "\n";
return ;
}
lst = i;
}
cout << 1 << "\n";
}
signed main() {
fre(test);
ios::sync_with_stdio(false);
cin.tie(nullptr);
int T = 1;
while (T--) {
solve();
}
return 0;
}J. 公路
拆贡献。枚举每一种颜色（即边权），把和该颜色相同的边全部拆掉，整棵树被拆分为若干连通块，设每个连通块的点数分别为 \(T_1,T_2,\ldots,T_m\)。那么，这种颜色的贡献就是： \[ n(n-1)-\sum_{i=1}^{m}T_i(T_i-1) \] 最终的答案就是每种颜色的贡献之和。
选定任意一个点为根，一个朴素的想法是对每种颜色建出虚树（取对应颜色的边下面的点，以及根节点），这确实是可行的。
设 \(sz[x]\) 表示以 \(x\) 为根的子树大小，称虚树上在我们选取的点集中的点称为黑点（特别的，包括根节点），其它点称为白点。
那么我们可以对每个黑点 \(x\) 算出它所在的连通块的大小，即 \[ sz[x]-\sum_{y,\ y\text{ 是 } x \text{ 子树中的黑点 }, \text{ 且 } x\to y \text{ 的路径上没有其它黑点}} sz[y] \] 具体的，如果 \(y\) 上面的点是白点，就可以把 \(sz[y]\) 传递上去。
时间复杂度 \(O(n\log n)\)，但实际 T 了，跑了 1.1s。
下面的代码经过刻意卡常，洛谷上跑了 820ms。
Code
#include <bits/stdc++.h>
using namespace std;
#define fre(x) freopen(#x".in", "r", stdin); freopen(#x".out", "w", stdout)
#define ck(x) { cout << "check " << x << endl;}
constexpr int N = 5e5 + 5;
vector<int> col[N];
vector<array<int, 2>> adj[N];
int tim, tot, fa[N][20], sz[N], dfn[N], dep[N], id[N], rid[N], f[N];
bool inTree[N];
using _node = vector<vector<int>>;
struct VirtualTree {
int n;
VirtualTree(int size) {
this->n = size;
}
void add(int x, int y, int w) {
adj[x].push_back({y, w});
adj[y].push_back({x, w});
}
void dfs(int x, int fath) {
dfn[x] = ++tim;
fa[x][0] = fath;
dep[x] = dep[fath] + 1;
sz[x] = 1;
for (int i = 1; i <= __lg(dep[x]) + 1; i++) {
fa[x][i] = fa[fa[x][i - 1]][i - 1];
}
for (auto [y, w] : adj[x]) {
if (y != fath) {
col[w].push_back(y);
dfs(y, x);
sz[x] += sz[y];
}
}
}
void init(int rt) {
dfs(rt, 0);
}
int LCA(int x, int y) {
if (dep[x] < dep[y]) {
swap(x, y);
}
while (dep[x] > dep[y]) {
x = fa[x][__lg(dep[x] - dep[y])];
}
if (x == y) {
return x;
}
for (int i = __lg(dep[x]); i >= 0; i--) {
if (fa[x][i] != fa[y][i]) {
x = fa[x][i];
y = fa[y][i];
}
}
return fa[x][0];
}
vector<int> b;
void Add(_node &Adj, int x, int y) {
// cout << "Add (" << x << " -> " << y << ")\n";
if (id[x] == 0) {
id[x] = ++tot;
rid[tot] = x;
b.push_back(x);
}
if (id[y] == 0) {
id[y] = ++tot;
rid[tot] = y;
b.push_back(y);
}
Adj[id[x]].push_back(id[y]);
}
void Del() {
while (!b.empty()) {
id[b.back()] = 0;
b.pop_back();
}
tot = 0;
}
_node getTree(vector<int> &a) {
Del();
int sz = 2 * a.size() + 1;
int top = 1;
sort(a.begin(), a.end(), [&] (const int &i, const int &j) {
return dfn[i] < dfn[j];
});
_node Adj(sz + 1);
vector<int> stk(sz + 1);
stk[top] = 1;
for (auto x : a) {
if (x == 1) {
continue;
}
int lca = LCA(x, stk[top]);
if (lca != stk[top]) {
while (top > 1 && dfn[stk[top - 1]] > dfn[lca]) {
Add(Adj, stk[top - 1], stk[top]);
top--;
}
if (lca != stk[top - 1]) {
Adj[id[lca]].clear();
Add(Adj, lca, stk[top]);
stk[top] = lca;
} else {
Add(Adj, lca, stk[top]);
top--;
}
}
Adj[id[x]].clear();
stk[++top] = x;
}
while (top > 1) {
Add(Adj, stk[top - 1], stk[top]);
top--;
}
return Adj;
}
};
//-------------- templates above --------------
void solve() {
int n;
cin >> n;
VirtualTree G(n);
for (int i = 1; i < n; i++) {
int x, y, w;
cin >> x >> y >> w;
G.add(x, y, w);
}
G.init(1);
long long ans = 0;
for (int i = 1; i <= n; i++) {
if (col[i].empty()) {
continue;
}
long long res = 1ll * n * (n - 1);
col[i].push_back(1);
for (auto x : col[i]) {
inTree[x] = true;
}
auto Adj = G.getTree(col[i]);
auto dfs = [&] (auto self, int x) -> void {
if (inTree[rid[x]]) {
f[x] = sz[rid[x]];
} else {
f[x] = 0;
}
for (auto y : Adj[x]) {
self(self, y);
if (!inTree[rid[x]]) {
f[x] += f[y];
}
}
if (inTree[rid[x]]) {
int g = f[x];
for (auto y : Adj[x]) {
g -= f[y];
}
res -= 1ll * g * (g - 1);
}
};
dfs(dfs, id[1]);
for (auto x : col[i]) {
inTree[x] = false;
}
ans += res;
}
cout << ans << "\n";
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int T = 1;
while (T--) {
solve();
}
return 0;
}【题解】2025 蓝桥杯国赛 CA
https://kisuraop.github.io/posts/c80723a0.html