10.3 Evening

Note

Problem 3

$N$个点$M$条边的带权无向图，询问那些边一定在最小生成树上，哪些边一定在最小生成树上，那些边一定不在最小生成树上。

我们将所有的边分为三类：一定在，可能在，一定不在。
那么我们首先建出一个最小生成树。然后我们知道在这个树上的边要么是一定在，要么是可能在。那么我们考虑一个最小生成树之外的边$V1$，然后我们知道这个边会使这个最小生成树形成一个环。我们找到这个环上面的最大的边$V2$，那么$V1 >= V2$， 我们考虑相等的情况，可以发现，如果用$V1$去替换$V2$，其实没有什么区别，所以$V1$和$V2$都是可能在。然后如果$V1$ $>$ $V2$

算法流程：
1. 随意构造一颗最小生成树。
2. 按边权顺序枚举剩下的边。
3. 与树上构成的环边进行比较判断。
4. 用并查集维护做到$O(N)$。

Problme 5

$N$个点$M$条边的带权无向图，有$Q$个询问，问每次删除一条边后的生成树大小。（访问相互独立）其中$N$ $<=$ $50000$, $M$ $<=$ $100000$

当然首先还是构造一个最小生成树，然后我们判断要删除的边是不是在树上，如果不在，大小不变。如果在树上，我们就要找到一个树外最小的一个边来替换这个树上的被删边，那么就和上面的题一样可以用并查集维护答案了。

算法流程：
1. 构建最小生成树
2. 如果被删边不在树上，不管。
3. 如果在树上，使用并查集维护答案。

Problem 8（Link）

$A$国：每一个人有一个友善值$Data[$ $]$,当两个人$(Data[i]$ ^ $Data[j])$ $%$ $2$ $==$ $1$的时候，$i$, $j$是朋友
$B$国：不同于A国，当两个人的$(Data[i]$ ^ $Data[j])$ $%$ $2$ $==$ $0$的时候或者$i$ $or$ $j$。然后给你一些$A$国人与$B$国的一些人的朋友关系，问最大朋友圈的人数。

最大团问题是典型的$NPC$问题。$NPC$问题基本都是只能暴力，但是有一个意外：二分图上面的NPC问题。而二分图上面的最大团就是其补图的最大独立集。看到了NPC问题并且数据范围又不算小，那么就压考虑二分图匹配。
至于怎么二分图。首先考虑A国，我们知道当两个人$(Data[i]$ ^ $Data[j])$ $%$ $2$ $==$ $1$的时候，$i$, $j$是朋友，那么最大团就只能有两个。因为如果i和j是朋友而第三个人k是奇数，那么k只能和其中之一为朋友，但和另一个不是。所以A的最大团只能有两个人，那么由于数据范围比较小，我们可以直接枚举。
那么B国的人呢？首先考虑第一个条件，我们知道了$B$国的所有偶数友善值的人都是朋友，所有奇数友善值的人都是朋友，那么我们将$B$图建成一个类似于二分图的形态，奇数在一边，偶数在一边，那么所有的奇数连起来，所有的偶数连起来。那么我们考虑第二个条件。因为奇偶两边都满了，所以最后一个限制只能在奇偶之间发挥作用。那么我们可以考虑匹配。但是这并不是一个二分图呀。所以我们考虑建补图，然后匹配后我们假设中间有$K$条边，奇数组有$Q$个数，偶数组有$P$个数，然后我们依照最大流最小割原理可以得到原图的最大团就是$P$ $+$ $Q$ $-$ $K$ 。

Problem ？

有一棵树，有一些节点上长了葱，这些葱可以让距离它距离不超过2的节点上全部长满葱，问至少要种多少颗葱才能让整个树都长满树。

我们按照大体的观念来看，哪一个节点是最难被覆盖的呢？直觉上来看

Problem 18

你有一个图，每条边有一个性质：颜色。分为黑色和白色