AtCoder Beginner Contest 451 复盘笔记

比赛链接：AtCoder Beginner Contest 451
原始代码：7.27 目录
整理日期：2026-07-30

总结

题目核心知识点本次情况复杂度
A - illegal字符串长度、取模独立 AC$O(
B - Personnel Change计数、差分思想独立 ACO(N+M)O(N+M)
C - Understorymultiset、upper_bound、区间删除独立 ACO(Qlog⁡Q)O(Q\log Q)
D - Concat Power of 2按位数 DP、字符串拼接、集合去重独立推出阶段思路但未完成；题解后抄写并默写约 O(Slog⁡S)O(S\log S)
E - Tree Distance树距离矩阵、祖先判定、构造后验证AI 题解后抄写并默写O(N2)O(N^2)
F - Make Bipartite 3动态二分图、并查集、启发式合并AI 题解后抄写并默写O(Qα(N)+Nlog⁡2N)O(Q\alpha(N)+N\log^2N)
G - Minimum XOR Walk生成树异或、异或线性基、01-Trie阅读官方代码；因未学 Trie 战略性放弃改错O((N+M)log⁡W)O((N+M)\log W)

这场最值得保留的经验：

  1. D 题中“按十进制位数分阶段”方向是对的，真正困难的是不同拆分会生成同一个数，不能只用简单乘法统计数量。数据量允许时，直接构造全部状态更稳。
  2. E 题给的是树上两点距离矩阵，不是图的邻接矩阵。正确方向是从距离反推唯一的候选树，再完整验算，而不是跑 Floyd。
  3. F 题的 color0/color1 是每个连通块内部的一组二分标签。不同块尚未合并时不需要讨论统一的“实际颜色”；加边时只需选择是否整体翻转一个块，使新边两端标签相反。
  4. 小集合向大集合合并不仅是一句优化口号。必须确保真正被移动的是较小连通块中的元素，否则复杂度保证会失效。
  5. G 题同时依赖异或线性基和 01-Trie。当前缺少前置知识时先记录问题转化，不强行背官方代码。

A - illegal

题意

若字符串长度是 55 的倍数，就违反法律并输出 Yes；否则输出 No。

约束为 1≤∣S∣≤101\le |S|\le10。

思路

直接判断

∣S∣ mod 5=0.|S|\bmod 5=0.

我的代码

#include <bits/stdc++.h>
using namespace std;

void solve()
{
    string s;cin>>s;
    if(s.size()%5==0) cout<<"Yes"<<"\n";
    else cout<<"No"<<"\n";
}

int main()
{
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    solve();
    return 0;
}

易错点

  • 题目问的是“是否违法”，所以整除时输出 Yes。
  • s.size() 返回无符号类型，但这里只与常数取模，不会产生问题。

B - Personnel Change

题意

有 NN 名员工、MM 个部门。员工 ii 本期属于 AiA_i，下期属于 BiB_i。对每个部门 jj 输出

下期人数j−本期人数j.\text{下期人数}_j-\text{本期人数}_j.

思路

分别统计每个部门本期和下期的人数。每读入一名员工，就执行

now⁡[Ai]++,nxt⁡[Bi]++.\operatorname{now}[A_i]++,\qquad \operatorname{nxt}[B_i]++.

最后逐个输出 nxt[i]-now[i]。

也可以只维护一个数组：离开原部门时减一，进入新部门时加一。

我的代码

#include <bits/stdc++.h>
using namespace std;
const int N=110;
int now[N],nxt[N];
int n,m;

void solve()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        int a,b;
        cin>>a>>b;
        now[a]++,nxt[b]++;
    }
    for(int i=1;i<=m;i++)
    {
        cout<<nxt[i]-now[i]<<"\n";
    }
}

int main()
{
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    solve();
    return 0;
}

复杂度

T=O(N+M),S=O(M).T=O(N+M),\qquad S=O(M).

C - Understory

题意

花园初始没有树，共有 QQ 次操作：

  • 1 h：加入一棵高度为 hh 的树；
  • 2 h：删除所有高度不超过 hh 的树。

每次操作后输出剩余树的数量。树高可以重复。

思路

需要维护一个有序、允许重复的集合，因此使用 multiset。

对删除操作，upper_bound(h) 返回第一个严格大于 hh 的元素位置，所以区间

[s.begin(),s.upper_bound(h))

恰好是所有满足 x≤hx\le h 的元素。直接删除这个半开区间即可。

我的代码

#include <bits/stdc++.h>
using namespace std;

void solve()
{
    int Q;cin>>Q;
    multiset<int> s;
    while(Q--)
    {
        int ops,h;
        cin>>ops>>h;
        if(ops==1)
        {
            s.insert(h);
            cout<<s.size()<<"\n";
        }
        else
        {
            ////注意索引越界!!!!!!
            if(s.empty())
            {
                cout<<0<<"\n";
                continue;
            }
            ////这里必须用upper_bound!!!!!!!!!!
            //不能用lower_bound
            auto it=s.upper_bound(h);
            s.erase(s.begin(),it);
            cout<<s.size()<<"\n";
        }
    }
}

int main()
{
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    solve();
    return 0;
}

为什么不能用 lower_bound

  • lower_bound(h)：第一个 ≥h\ge h 的位置，删除其前面只能删掉 <h<h；
  • upper_bound(h)：第一个 >h>h 的位置，删除其前面才能删掉 ≤h\le h。

本题要求高度不超过 hh，所以必须用 upper_bound。

multiset::erase(first,last) 的代价与查找和实际删除元素数有关。每棵树只会被插入一次、删除至多一次，因此总复杂度可写为

T=O(Qlog⁡Q),S=O(Q).T=O(Q\log Q),\qquad S=O(Q).

D - Concat Power of 2

本题独立想到了按十进制位数分阶段，但因为去重计数写不出而停止；之后看题解代码、抄写并独立默写。

题意

选择一个或多个 22 的幂，将它们的十进制字符串任意排列、允许重复地拼接起来，得到一个“好整数”。求第 NN 小的好整数。题目保证答案不超过 10910^9。

例如：

1,2,4,8,11,12,14,16,18,21,…1,2,4,8,11,12,14,16,18,21,\ldots

我的初始思路

最初注意到可以按 10k10^k 划分位数阶段，并尝试只计算每一阶段的状态数，再二分定位第 NN 个数所在阶段。这个方向与官方的“按位数递推”有共同点，但存在两个问题：

  1. 题目保证的是第 NN 个好整数的数值不超过 10910^9，不是 N≤109N\le10^9；实际只有约 125125 万个候选，完全可以全部生成。
  2. 不同切分方式可能生成同一个数。例如
1∥64=16∥4=164.1\Vert64=16\Vert4=164.

因此不能写成简单的数量递推。只算个数仍然必须处理去重，而去重通常意味着保留足够多的实际状态。

原代码里的 calc(val) 若用于判断一个数能否拆成若干个 22 的幂字符串，可以写字符串划分 DP；但若从 11 枚举到 10910^9 再调用它，复杂度仍不可接受。更好的策略是从合法状态出发直接生成。

按位数 DP

定义：

  • PiP_i：所有恰好为 ii 位的 22 的幂；
  • XkX_k：所有恰好为 kk 位的好整数；
  • X0={0}X_0=\{0\}，其中 00 只代表空串，不是一个好整数。

枚举最后拼接的 22 的幂长度 ii，则

Xk=⋃i=1k{x⋅10i+p∣x∈Xk−i, p∈Pi}.X_k= \bigcup_{i=1}^{k} \left\{ x\cdot10^i+p \mid x\in X_{k-i},\ p\in P_i \right\}.

这个式子的核心是数位对齐：

  • x∈Xk−ix\in X_{k-i}，乘 10i10^i 后给末尾空出 ii 位；
  • p∈Pip\in P_i，恰好填满这 ii 位；
  • 枚举 i=1…ki=1\ldots k，等价于枚举最后一段的所有可能长度；
  • set 对不同切分产生的相同整数去重。

当 i=ki=k 时使用 X0X_0，生成只由一个 kk 位的 22 的幂构成的好整数。因此循环必须写成 i<=k。

最后把 X1,…,X9X_1,\ldots,X_9 汇总，答案是 ans[n-1]。代码又执行了一次 sort，这样写没有问题，但在当前实现中其实不是必需的：不同位数的正整数天然按位数递增，而每个 X[k] 本身又是有序的 set。保留 sort 可以让“最终按数值取第 NN 小”这一意图更直观，也不必依赖上述有序性。

默写代码

#include <bits/stdc++.h>
using namespace std;
#define int long long

void solve()
{
    int n;cin>>n;
    //按位存储2的幂
    vector<int> pow2[10];
    for(int i=0;;i++)
    {
        int p=1LL<<i;
        if(p>1e9) break;
        int len=to_string(p).size();
        pow2[len].push_back(p);
    }

    //存储10的n次方
    vector<int> pow10(10);
    pow10[0]=1;
    for(int i=1;i<10;i++) pow10[i]=pow10[i-1]*10;

    vector<set<int>> X(10);
    //X[i]:存储长度为i的好数
    //X[0].push_back(0);-->完全错误的写法!!!!!!!
    X[0].insert(0);

    for(int k=1;k<10;k++)
    {
        for(int i=1;i<=k;i++)
        {
            for(auto x:X[k-i])
            {
                for(auto p:pow2[i])
                {
                    int val=x*pow10[i]+p;
                    if(val<1e9) X[k].insert(val);
                }
            }
        }
    }

    vector<int> ans;
    for(int i=1;i<10;i++)
    {
        for(auto x:X[i]) ans.push_back(x);
    }
    //虽然set默认有序,但是放个sort在这更直观
    sort(ans.begin(),ans.end());

    cout<<ans[n-1]<<"\n";
}

signed main()
{
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    solve();
    return 0;
}

对话中的 MLE 复盘

最后一次错误提交被描述成 MLE，但根因不是集合真的占满了 1024 MiB1024\text{ MiB}，而是越界导致未定义行为：

vector<set<int>> X(10);
for(int k=1;k<=10;k++) //访问了X[10]

合法下标只有 0…90\ldots9，应写 k<10。此外，构造时写成 i<k 会漏掉单独一个 22 的幂，必须是 i<=k。

这里的经验是：评测显示 MLE 不代表根因一定是内存复杂度。发生数组或容器越界后，RE、MLE、WA 都可能只是未定义行为的外在表现。

速刷时再次确认的错误：为什么必须 set

速刷代码在这里专门标记了：

////这里必须用set来存储(去重)
vector<set<int>> good(10);

同一个整数可能有不同的拼接方式。例如 128 既可以看成一个单独的 22 的幂，也可以看成

12∥8=128,12\Vert 8=128,

其中 12 又来自 1∥21\Vert 2。因此递推枚举的是“所有生成方式”，而 X_k/good[k] 需要保存的是“所有不同的数”，两者不能混为一谈。若换成普通 vector 而不去重，最后的第 NN 小会把同一个数重复计数。

复杂度

设最终生成的不同状态总数为 SS，实际约为 1.26×1061.26\times10^6。set 插入和最后排序均带对数因子，可概括为

T=O(Slog⁡S),S=O(S).T=O(S\log S),\qquad S=O(S).

E - Tree Distance

本题为 AI 题解后抄写，再独立默写。对话中最重要的转变是分清“距离矩阵”和“邻接矩阵”。

题意

输入 NN 个顶点两两之间的距离 Ai,jA_{i,j}，判断是否存在一棵正边权无向树，使树上任意两点的唯一路径长度都等于给定的 Ai,jA_{i,j}。

题目不是给图求最短路，而是给出完整距离表，要求判断它能否由一棵树产生。

为什么 Floyd 方向不对

输入的 Ai,jA_{i,j} 已经是两点间距离，不是边权。若把所有 Ai,jA_{i,j} 都当成边建完全图再跑 Floyd，检查到的只是这个完全图中的最短路性质，并没有构造出只有 N−1N-1 条边的树。

树上两点间只有一条简单路径，所以这里应利用路径的可加性反推父子关系。

以 1 为根构造候选树

固定顶点 11 为根。对任意 i≠1i\ne1，若 jj 位于根到 ii 的路径上，则必有

A1,j+Aj,i=A1,i.A_{1,j}+A_{j,i}=A_{1,i}.

反过来，在合法树距离中，满足该式的 jj 就在根到 ii 的路径上。由于所有边权均为正，这条祖先链上越靠近 ii 的点，Aj,iA_{j,i} 越小。因此父节点为(该公式中的arg min为约束条件，返回值为下标j)

parent⁡(i)=arg⁡min⁡j≠i, A1,j+Aj,i=A1,iAj,i.\operatorname{parent}(i) =\arg\min_{j\ne i,\ A_{1,j}+A_{j,i}=A_{1,i}} A_{j,i}.

边权就是

w(i,parent⁡(i))=Ai,parent⁡(i).w(i,\operatorname{parent}(i))=A_{i,\operatorname{parent}(i)}.

在合法输入中，最小者不会并列：所有祖先位于同一条路径，正边权保证它们到 ii 的距离严格不同。非法输入可能出现代数上的并列，此时任取一个候选，最后的完整验证会判掉。

为什么还要完整验证

局部满足祖先等式，只能构造出一个候选树，不能保证输入的每一项都一致。因此从每个根 root 做一次 DFS，算出候选树中的全部距离，并检查

dist⁡candidate(s,t)=As,t\operatorname{dist}_{\text{candidate}}(s,t)=A_{s,t}

是否对所有点对成立。

这是典型的“构造 + 验证”：构造阶段利用必要结构恢复唯一候选，验证阶段负责排除所有非法距离矩阵。

默写代码

#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> PII;
const int N=3e3+10;
int a[N][N];
int n;
int parent[N];
vector<PII> g[N];

void solve()
{
    cin>>n;
    for(int i=1;i<n;i++)
    {
        for(int j=i+1;j<=n;j++)
        {
            int w;cin>>w;
            a[i][j]=a[j][i]=w;//存无向边
        }
    }

    //确定2~n每个节点的父节点
    //和从上往下,父节点是离子节点最近的
    //利用a[1][i]=a[1][j]+a[j][i]
    for(int i=2;i<=n;i++)
    {
        int fa=-1;
        int fa_dist=INT_MAX;//初始化为无穷大

        for(int j=1;j<=n;j++)
        {
            if(j==i) continue;
            if(a[1][j]+a[j][i]!=a[1][i]) continue;//不是1~i路径上的

            if(a[j][i]<fa_dist)
            {
                fa=j;
                fa_dist=a[j][i];
            }
        }

        //如果某个子节点不存在父节点
        if(fa==-1)
        {
            cout<<"No"<<"\n";
            return;
        }

        parent[i]=fa;
    }

    //利用每个点的父节点,将所有零散的点连成一棵树(邻接表)
    for(int i=2;i<=n;i++)
    {
        int fa=parent[i];
        int w=a[fa][i];
        g[i].emplace_back(fa,w);//存边方便后续dfs取出来
        g[fa].emplace_back(i,w);
    }

    //与已有的a[i]数组意义核对
    //用dfs遍历1~n每个节点
    for(int root=1;root<=n;root++)
    {
        vector<int> dist(n+1,-1);
        stack<int> st;
        st.push(root);
        dist[root]=0;

        //栈式dfs
        while(!st.empty())
        {
            int u=st.top();
            st.pop();

            //求root到各个点的距离
            //C++17结构化绑定
            for(auto [v,w]:g[u])
            {
                //已经来过,直接continue
                if(dist[v]!=-1) continue;

                dist[v]=dist[u]+w;
                ////忘记入栈了 艹
                st.push(v);////写掉了
            }
        }

        //把dist[i]与a[roo][i]一一对照
        for(int i=1;i<=n;i++)
        {
            if(dist[i]!=a[root][i])
            {
                cout<<"No"<<"\n";
                return;
            }
        }
    }

    cout<<"Yes"<<"\n";
    return;
}

int main()
{
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    solve();
    return 0;
}

默写时的错因

第一次默写 DFS 时只写了

dist[v]=dist[u]+w;

却漏掉 st.push(v)。这样只会处理根的直接邻居，无法继续访问更深的节点。以后写非递归 DFS 时，应把一次发现新点的完整动作绑定起来：

  1. 标记或写入距离；
  2. 入栈；
  3. 之后再由栈弹出并扩展。

速刷时暴露的三个边界错误

速刷版又把这三个地方明确标了出来：

  1. 读取上三角矩阵的循环边界：输入只有 i<ji<j 的项，所以读取应写成

    for(int i=1;i<n;i++)

    写成 i<=n 虽然最后一轮没有新的 j，但它不符合输入结构，也容易掩盖真正的边界。

  2. 每次 DFS 的距离数组必须初始化为 -1：-1 同时表示“尚未访问”。如果使用未初始化数组，或没有为所有位置设为 -1，就不能可靠地区分“未访问”和合法距离。

  3. 发现新点后必须入栈：

    dist[v]=dist[u]+w;
st.push(v);

    只更新 dist[v] 而不 push，遍历会在根的一层邻居后停止；这正是原默写代码中反复出现的错误。

复杂度

找父节点需要 O(N2)O(N^2)；候选树只有 N−1N-1 条边，从每个点做一次 DFS 也是 O(N2)O(N^2)：

T=O(N2),S=O(N2).T=O(N^2),\qquad S=O(N^2).

F - Make Bipartite 3

本题为 AI 题解后抄写，再独立默写。代码选用注释最详细的 默写过一遍思路.cpp。

题意

初始有 NN 个点、没有边。每次加入一条无向边后：

  • 若当前图不是二分图，输出 −1-1；
  • 否则输出合法二染色中最少的黑点数量。

加边后不会删除边，因此一旦出现奇环，以后永远不是二分图。

静态问题：一个连通块贡献多少

一个连通二分图的二染色划分唯一到整体翻转。设两侧顶点数为 c0,c1c_0,c_1，可以任选其中一侧作为黑色，所以该连通块的最小黑点数为

min⁡(c0,c1).\min(c_0,c_1).

不同连通块之间可以独立翻转，因此全图答案为

ans⁡=∑Cmin⁡(∣C0∣,∣C1∣).\operatorname{ans} =\sum_{C}\min(|C_0|,|C_1|).

这可以理解为连通块之间彼此独立的局部最优；合并两个块时，用

ans⁡←ans⁡−contrib⁡(A)−contrib⁡(B)+contrib⁡(A∪B)\operatorname{ans} \leftarrow \operatorname{ans} -\operatorname{contrib}(A) -\operatorname{contrib}(B) +\operatorname{contrib}(A\cup B)

维护即可。

动态加边的两种情况

设 u,v 所在连通块根分别为 uu,vv。

已在同一个连通块

  • 若二者标签不同，新边合法，划分不变；
  • 若二者标签相同，新边与已有路径组成奇环，令 ans=-1。由于之后只加边，后续全部输出 −1-1。

位于不同连通块

两个块之间原本没有任何约束，所以它们各自的 0/10/1 标签方向可以独立选择：

  • 若 u,v 当前标签不同，直接把两块的同号标签合并；
  • 若 u,v 当前标签相同，先整体翻转其中一个块，即交换该块的 color0 与 color1，再按同号标签合并。

这样合并后 u,v 必然处于不同集合，新边合法。

“标准、标签、实际颜色”的严格解释

对话中围绕这个问题反复讨论，容易越说越绕。最简单且严格的理解是：

  1. color0[root] 和 color1[root] 只是当前连通块内部二分图的两侧，标签 0/10/1 本身没有黑白含义。
  2. 两个连通块还没连接时，不存在必须统一的跨块“实际颜色标准”；两块都可以独立整体翻转。
  3. 新边第一次把两个块联系起来，此时我们选择一个相对方向：让新边两端落在不同标签中。
  4. swap(color0[subRoot],color1[subRoot]) 是把子块整个二分划分翻转。它不破坏子块内部任何边的异色关系。
  5. 完成对齐后，才把两块的 color0 合并、color1 合并，形成新连通块的一套统一标签。

因此 same_color 更准确的名字是 same_label。当两点来自不同块时，它不是在判断某种预先存在的全局黑白颜色，只是在决定合并前是否需要翻转一个块。

最终想通的视角：从合并后往前推

追加对话记录：F 题后续 DeepSeek 对话

昨天反复纠结的原因，是一直试图从前往后理解：合并前 A、B 两个连通块的 color0/color1 分别对应什么颜色，u,v 此时到底算不算同色。但两个块尚未联通，各自都能独立翻转，跨块比较“实际颜色”本来就没有固定意义。

更顺畅的理解方式是从合并后的要求往前倒推：

加入边 (u,v)(u,v) 后，u 和 v 必须落在新连通块的两个不同标签集合中。

后面的集合合并固定采用

C0=A0∪B0,C1=A1∪B1.C_0=A_0\cup B_0,\qquad C_1=A_1\cup B_1.

因此只需在执行这一步之前把 B 的标签方向对齐好：

合并前 u,v 的标签是否翻转 B合并后的结果
不同不翻转分别进入 C0,C1C_0,C_1，满足异色
相同交换 B0,B1B_0,B_1v 的标签取反，再分别进入 C0,C1C_0,C_1，满足异色

所以“让 u,v 标签不同”不是在描述两个独立块合并前已有的全局颜色事实，而是在构造合并后的合法二染色。代码里的 is_same 决定的只是：为了让最终状态合法，合并前是否需要交换子块的两个状态集合。

为什么要小并大

若每次翻转和移动任意一个块，单次可能达到 O(N)O(N)，总复杂度可能退化为 O(N2)O(N^2)。

始终把较小连通块的元素移动到较大块后，每个顶点每被移动一次，所在块大小至少翻倍：

1→2→4→8→⋯→N.1\to2\to4\to8\to\cdots\to N.

所以每个顶点最多被移动 O(log⁡N)O(\log N) 次。使用 set::merge 时，每次节点转移还有平衡树操作的对数代价，因此 C++ 实现可保守记为

T=O(Qα(N)+Nlog⁡2N).T=O(Q\alpha(N)+N\log^2N).

官方题解把“扫描较小块”的顶点总数记为 O(Nlog⁡N)O(N\log N)；若集合合并操作按实现作更细分析，还需计入 set 的对数因子。

默写代码

#include <bits/stdc++.h>
using namespace std;
//用并查集来维护联通状态
class UnionSet
{
public:
    vector<int> fa,sz;
    UnionSet(int n):fa(n+1),sz(n+1)
    {
        for(int i=0;i<=n;i++)
        {
            fa[i]=i;
            sz[i]=1;
        }
    }
    int get(int x)
    {
        return fa[x]=(x==fa[x]?x:get(fa[x]));
    }
    int merge(int a,int b)
    {
        int aa=get(a),bb=get(b);
        if(aa==bb) return bb;
        if(sz[aa]>sz[bb])
        {
            fa[bb]=aa;
            sz[aa]+=sz[bb];
            return aa;
        }
        else
        {
            fa[aa]=bb;
            sz[bb]+=sz[aa];
            return bb;
        }
    }
};
void solve()
{
    int n,q;
    cin>>n>>q;

    UnionSet uf(n);
    //用set自动去重,避免一个元素多次加入导致size计算不准确
    //color[root]:以root为根节点,与root联通的所有点集
    //color0:颜色标签为0,color1:颜色标签为1
    vector<set<int>> color0(n+1),color1(n+1);
    //初始化
    for(int i=1;i<=n;i++) color0[i].insert(i);//set要用insert

    int ans=0;
    while(q--)
    {
        int u,v;
        cin>>u>>v;

        if(ans==-1)
        {
            cout<<"-1"<<"\n";
            continue;
        }

        int uu=uf.get(u),vv=uf.get(v);
        //通过两者颜色标签是否为0来判断两者标签是否相同
        bool u_is0=color0[uu].count(u);
        bool v_is0=color0[vv].count(v);
        bool is_same=(u_is0==v_is0);
        //如果u,v本来就联通
        if(uu==vv)
        {
            //如果颜色相同,则后续一直为非法状态,全输出-1即可
            if(is_same) ans=-1;
            cout<<ans<<"\n";//不相同就不影响黑点个数,依然还是ans
            continue;
        }

        //如果u,v不联通
        //我们先减去合并前两个联通块的黑点数,最后再加上合并后的黑点数
        //局部贪心思想,取min,因为我大可以通过翻转颜色来使每个分散的联通块黑点个数最少,从而达到总体最小
        ans-=min(color0[uu].size(),color1[uu].size());
        ans-=min(color0[vv].size(),color1[vv].size());

        //确定大小根-->小并大,set::merge效率更高
        int mainRoot=uu,subRoot=vv;
        int newRoot=uf.merge(uu,vv);
        int oldRoot=(newRoot==mainRoot?subRoot:mainRoot);
        //通过返回值来确定大小-->newRoo.size()t>oldRoot.size()

        //若标签相同,则翻转
        if(is_same)
        {
            swap(color0[oldRoot],color1[oldRoot]);
        }

        //然后直接调用set里面的merge方法来合并集合,而不是范围for+insert/erase
        color0[newRoot].merge(color0[oldRoot]);
        color1[newRoot].merge(color1[oldRoot]);
        color0[oldRoot].clear();
        color1[oldRoot].clear();

        ans+=min(color0[newRoot].size(),color1[newRoot].size());

        cout<<ans<<"\n";
    }
}

int main()
{
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    solve();
    return 0;
}

速刷时的实现提醒：集合初始化也要保持不变量

速刷代码在初始化处写了：

//记得去重
vector<set<int>> color0(n+1),color1(n+1);
for(int i=1;i<=n;i++) color0[i].insert(i);//初始化

这里的重点不只是“容器选 set”，还包括初始化不变量：每个单点连通块的唯一顶点必须先进入 color0[i]，color1[i] 为空。之后 count(u) 才能判断某点当前是否属于标签 0；如果漏初始化、把根下标写错，后面的 same_label 判断和答案贡献都会一起失效。

代码细节复盘

  • merge 返回新根很重要，因为颜色集合必须挂到真实的新根上。
  • oldRoot 是并查集合并后失去根身份的旧根，也是需要移动颜色集合的块。
  • 注释 newRoot>oldRoot 不准确：根的选择依据是 sz，不是编号大小；代码本身没有依赖编号关系。
  • 大小相等时模板让第二个根成为新根，这仍符合小并大，因为两块等大，移动任意一边都满足复杂度证明。
  • set::merge 是 C++17 接口，编译时需要使用 C++17 或更新标准。
  • 对话中曾把一次 TLE 归因于多一次 get 或少数几次自合并，这个解释证据不足。真正需要检查的是：每次是否只移动较小块、旧根集合是否正确清空、是否意外反复移动大块。

G - Minimum XOR Walk

本题只保留官方思路地图。当前尚未学习 01-Trie，也需要异或线性基作为前置，因此战略性放弃改错。

题意

给定带权连通无向图。一次 walk 的权值是经过边权的异或和，允许重复经过顶点和边。统计满足以下条件的点对 (x,y)(x,y)：从 xx 到 yy 的 walk 的最小可能异或值不超过 KK。

官方思路的四层转化

1. 固定生成树

令 AvA_v 为生成树上根 11 到顶点 vv 的路径异或值。对任意边 (u,v,w)(u,v,w)，定义环异或值

C=Au⊕Av⊕w.C=A_u\oplus A_v\oplus w.

生成树边的 C=0C=0；非树边的 CC 表示沿生成树路径和该边绕一圈所能额外加入的异或量。

2. 环异或构成线性空间

所有环值张成异或线性空间 S\mathcal S。任意从 uu 到 vv 的 walk 权值都可写为

Au⊕Av⊕s,s∈S.A_u\oplus A_v\oplus s,\qquad s\in\mathcal S.

因此最小 walk 权值为

f(Au⊕Av),f(x)=min⁡s∈S(x⊕s).f(A_u\oplus A_v), \qquad f(x)=\min_{s\in\mathcal S}(x\oplus s).

3. 用异或基约简代表元

官方证明了这里的最小代表元映射满足

f(x⊕y)=f(x)⊕f(y).f(x\oplus y)=f(x)\oplus f(y).

令

Bv=f(Av),B_v=f(A_v),

则点对条件化为

Bu⊕Bv≤K.B_u\oplus B_v\le K.

代码中通过

z=min(z,z^b);

依次用基向量约简，得到每个等价类的最小代表元。

4. 01-Trie 统计异或不超过 K 的点对

依次处理 BvB_v。查询 Trie 中已有多少个 xx 满足

x⊕Bv≤K,x\oplus B_v\le K,

再插入 BvB_v。这样每个无序点对恰好统计一次。

官方代码模块地图

  • a[v]：生成树上根到 vv 的路径异或；
  • a[x]^a[y]^w：边 (x,y,w)(x,y,w) 对应的环异或；
  • basis：这些环异或张成空间的一组约简基；
  • 对每个 a[v] 再执行 min(z,z^b)：求规范代表元 BvB_v；
  • BinaryTrie::count_leq(K,z)：统计已有值中与 zz 异或后不超过 KK 的数量。

为什么现在不继续改错

这题的关键前置不是语法，而是两个独立专题：

  1. 异或线性基：如何插入基、约简、证明可达异或空间；
  2. 01-Trie：如何按最高位到最低位统计 x⊕y≤Kx\oplus y\le K。

在这两个专题尚未学习时，修改官方代码容易变成背模板，无法解释核心不变量。当前先完成既定的 DP 后半段与线段树学习，再依次补 01-Trie、异或线性基，最后回看本题更合适。

另外，对话中 AI 最初给出的实现全 WA，随后对根因的解释也没有定位到确定差异。这再次说明：官方 AC 代码可以作为事实基准，但 AI 对 WA 原因的猜测必须通过反例或对拍验证，不能直接写入结论。

本场错因清单

题意与建模

  • D：把“第 NN 个好整数不超过 10910^9”误读成了“N≤109N\le10^9”，因此过早采用只计数的阶段压缩。
  • E：把树距离矩阵当成图的邻接矩阵，试图用 Floyd 验证最短路。
  • F：把不同连通块的内部标签误认为预先存在统一的全局黑白标准。

边界与未定义行为

  • C：删除 ≤h\le h 的元素必须使用 upper_bound(h)。
  • D：i<k 会漏掉单个 22 的幂，应为 i<=k。
  • D：X 大小为 1010 时访问 X[10] 越界；表面上的 MLE 实际可能来自未定义行为。
  • D（速刷）：同一个好整数可能由多种拼接方式生成，普通 vector 会重复计数，必须使用 set 或等价方式去重。
  • E（速刷）：读取距离矩阵时外层只需枚举 i<n；每轮 DFS 都要把 dist 初始化为 -1。
  • E：非递归 DFS 写入距离后忘记把新点压栈。
  • E（速刷）：再次漏写 st.push(v)，说明“更新距离 + 入栈”仍需作为一个不可拆分的遍历动作记忆。

数据结构不变量

  • F：颜色集合必须始终挂在当前并查集根上。
  • F（速刷）：每个单点块必须初始化为 color0[i]={i}, color1[i]=empty，否则标签查询的不变量从一开始就不成立。
  • F：合并后必须清空旧根集合，避免后续误用。
  • F：启发式合并的复杂度依赖“移动较小块”这一事实，不能只看变量名叫 mainRoot/subRoot。
  • G：线性基与 01-Trie 都有严格不变量，不能仅凭代码短就直接默写。

新知识专题

1. 构造后验证

当输入描述的是某个隐藏结构的全部观测值时，可以采用：

  1. 利用必要条件构造唯一或少量候选；
  2. 用原始定义完整验证候选。

E 题中，祖先距离等式负责构造父节点，全点对 DFS 距离负责验证。这种框架允许构造阶段对非法输入中的并列候选任取一个，因为最终验证会保证正确性。

2. 小并大

若要反复合并两个集合，始终把较小集合中的元素移动到较大集合。对任意元素，每次移动后所在集合大小至少翻倍，所以移动次数最多为

⌊log⁡2N⌋+1.\lfloor\log_2N\rfloor+1.

常见应用包括：

  • DSU 上维护成员集合；
  • 树上启发式合并；
  • 合并颜色计数、频率表或有序集合。

3. 二分图的整体翻转自由度

连通二分图的二染色只有两种，它们互为整体翻转。若两个连通块尚无边相连，则两块可以分别选择翻不翻；新边加入时，这个自由度正好用于让两个端点异色。

这个性质也是带奇偶关系并查集的基础。以后学“扩展域并查集”或“带权并查集”时，可以把 F 题改写成只维护每个点到根的颜色异或关系，并单独维护每个根两侧的计数，从而不必保存所有顶点集合。

赛后训练清单

  • 不看代码重写 C，并口述 lower_bound 与 upper_bound 的区别。
  • 用 164164 手推 D 中两种不同拆分为什么需要 set 去重。
  • 不看代码写出 D 的递推式，并解释 X0={0}X_0=\{0\} 为什么代表空串。
  • 检查 D 的两个循环边界：i<=k 与汇总时 k<10。
  • 用四个点画一棵带权树，手算 E 中每个点的祖先候选和父节点。
  • 独立重写 E 的非递归 DFS，把“写距离 + 入栈”作为一个完整动作。
  • 用两个二分连通块手推 F 的四种端点标签组合，以及何时交换 color0/color1。
  • 证明 F 中每个连通块对答案的贡献是 min⁡(∣C0∣,∣C1∣)\min(|C_0|,|C_1|)。
  • 检查 F 的并查集返回值，确认颜色集合始终合并到真实新根。
  • 完成当前 DP 后半段与线段树计划后，再学习 01-Trie、异或线性基并回看 G。