有以下引理：

不存在两个合法环，他们存在公共边。

证明：公共边边权为 \(z\)，第一个环除去公共边为 \(x\),第二个环除去公共边为 \(y\)。

则有 \(x \oplus z = 1\) \(y \oplus z = 1\),则存在另外一个简单环的权值为 \(x\oplus y = 0\),所以该图不合法。

我们知道一颗树上是没有环的。

所以一颗树不影响非树边的加入。

我们考虑先在这些边按照加边顺序里做一颗生成树出来。

这些边一定可以存在。

那么我们考虑那些非树边。

我们在加入一条非树合法边时，在 \((u,v)\) 这条路径上打上一个\(tag\)。

判断一条非树边是否合法时，我们可以查询 \((u,v)\) 是否有标记，并查询 \((u,v)\) 的异或和。

最新文章

1. ASP.NET MVC VS2010中更改默认调试浏览器
2. 转：详解Eclipse断点
3. OSGI入门笔记
4. mkdir:批量创建文件夹
5. THE ONE THING PEOPLE WILL MASSIVELY OVERPAY FOR (有一个东西人们是愿意出高价购买的)
6. [GRYZ2015]足球联赛
7. 使用flask的时候遇到的问题及其解答
8. Struts2 学习笔记18 拦截器原理分析
9. JAVA设计模式--辛格尔顿
10. Javascript 封装问题
11. [转]怎么查看和修改 MySQL 的最大连接数？
12. JavaScript篇 深入理解JavaScript函数
13. cadcam
14. Python-接口自动化（五）
15. HTML 转义字符对应表
16. Mac OS 中安装 autoconf 和 automake
17. javascript实现 color颜色格式转换【 rgb和十六进制的转换】
18. 华Xia相机WEB后台设置
19. Java自学路线
20. set_new_handler

热门文章

1. Windows10使用技巧
2. 学习手册 | MySQL篇 · 其一
3. 零基础入门C/C++实现你的浪漫表白：浪漫流星雨表白程序
4. Hdu P1394 Minimum Inversion Number | 权值线段树
5. u-boot 1.1.6 start.S 代码学习<转>
6. PWN二进制漏洞学习指南
7. cesium制作自己的骑行轨迹
8. Python小练习之验证“哥德巴赫猜想”
9. kafka的安装
10. ASP.NET Core设置URLs的几种方法