我们先不要管两个数按位与为\(1\)和两个数按位或为\(0\)的情况那么剩下的情况就是很简单的2-SAT问题就像并查集处理二元关系一样，这里最后建成的图一定是完全对称的，如下其中每个点都是一个SCC然后我们再来看剩下的两种情况，拿两个数按位与为\(1\)为例这就说明两个数必须要都是

详细阐述一下蓝书的做法首先，我们创造\(n\)个点，每个点有一个权值\(p_i\)，也有一个编号蓝书的连边就是对每一个点，从这个点出发连一条有向边到编号为这个点权值的点比如书上举的那个例子，编号分别为\(1,2,3,4,5,6\)，权值分别为\(2,4,6,1,5,3\)这样这个图肯定是由若干个环组成的然后

其实这个证明与前面那个证明很像假设最终生成的生成树不包含这\(m-k\)条边中连接生成森林的两个不连通节点的最小的边，那么我们从这些最小的边中任选一条边加入到树中会形成一个环，而且这个环（除了加入的这条最小边）一定存在一条边不是最开始的\(k\)条边中的某一条（因为如果这个环除了

这道题目真实绝了，这篇随笔主要是对蓝书上面的注释首先那个结论肯定要知道，然后选取\(1\)号点作为基准点也是想到了的那么接下来肯定就是把\(1\)号点所在连通块当做树根嘛，问题是怎么去分配剩下的点我最开始想的是像树形背包一样去DP，但是不知道具体有多少子树，然后我又想枚举子树个

这道题目二分的做法见蓝书介绍一个斜率优化的做法但是说实话，我是证明不了下面为啥直接取队头就可以解决问题了下面这张图片又在说什么。。。

最短Hamilton路径状压dp。设\(f_{S,i}\)表示走过的节点状态为\(S\)\((0\)为没走过，\(1\)为走过\()\)，当前在点\(i\)时的最小代价，显然\(S\)的第\(i\)位必须为\(1\)。那么\(f_{S,i}=\min_{S\operatorname{and}2^j=1,j\neqi}\lbracef_{S\operatorname{xor}