分类： 图论

一道不是那么传统的带权并查集

题目特殊的地方在于运算是异或，不是像经典的带权并查集那样可以有一个恒定的子节点与父结点的递推关系。比如传统的求一个结点到根结点的距离的并查集可以这样写

int findfat(int x)
{
	if(fat[x] == x) return x;
	int tmp=fat[x];
	fat[x]=findfat(fat[x]);
	//在此处修改val比如：
	value[x]=value[tmp]+1;
	return fat[x]; 
}

这样写的正确性在于这个递推关系一定是正确的，即使在森林里改变任意一个点的数值，在他的后代执行findfat的时候也一定能更新所有的数值。但是异或是不太一样的，如果直接写 value[x]=value[x]^value[tmp]，的话，仅仅是对x求两次查找根结点而不做任何其他操作就会使得数值出现错误，因为w[x]等于和自己又异或了一次，就会出现不正常的结果。

思考了一下，我直接把w数组定义为：w[i]表示 继续阅读“[数据结构][带权并查集][异或] UVALive 4487 Exclusive-OR”

利用并查集处理合并，并保存每个块对应的覆盖范围(在y轴上的)上下界；利用线段树（更新区间的范围从并查集维护的信息中得到）维护每个x.5的点对应的州数和城市数。区间修改单点查询，只要确定好x.5这些点在线段树中的对应的下标就可以了，我这里是x.5在线段树中下标为(x+1)。由于我写的是1-n的线段树写完了才发现题目说的0-n-1，只能把读进来的东西都++。具体的操作：对于road，先找两个点是否在一个块里，如果是了那就不用任何操作（画图可以看出来如果这俩是一个块里的那么他们覆盖范围之间一定已经有线了），否则先把这两个的分别的块对应的区域在线段树中减去他的影响，再将两个块合并之后，再在线段树中加上这一新块的影响。先减后加，这样就可以避免繁杂的分类讨论了。。。

第一版正经的线段树ac之后想了想感觉在这个情境下只需要保证叶子节点的信息有效就行了，推了一下感觉可以去掉maintain的操作。。。试了下果然可以，而且快了很多，在vjudge上已经是用线段树的跑的最快的了（前几名都是用的BIT emmm

wa的点：本来一气呵成写完很舒服但是没想到出了很多bug，因为一些愚蠢的bug调试了很久。。。。数据结构这块还是太弱了。
继续阅读“[线段树+][并查集][区间信息维护] UVALive 4730 Kingdom”

题意：求出给定图的生成子图里有多少个是仙人掌。

首先明确生成子图的概念：包括所有的顶点的子图（之前没有弄明白这个一直没有想出来），那么这个操作其实就很简单了，首先判断图形是否为仙人掌，如果是的话把其中所有的圈（其实在这里就是点双联通分量）所包含的边的数量算出来，Π(cnt[i]+1)即为结果（每个圈最多只能去掉一个边）。

首先，判断是否为仙人掌，这个可以利用无向图仙人掌的性质在dfs求双联通分量的时候顺便求出来：对于任意一个dfs树上的节点u，他的反向边数量+他的子节点中low值小于pre[u]的数量<2，如果大于等于2说明这个节点附近已经产生了两个环了，不可能是仙人掌，反之如果所有点都满足这个要求，那么一定是仙人掌。

其次，求每一个圈的边数。这里如果是仙人掌的话，一定每个点双联通分量都是一个圈（否则就会被判定为非仙人掌，所以这里首先保证第一步的正确性是很重要的），这样的话只需要在求点双联通分量时在退栈的时候把每个bcc对应的边的数量记录下来就可以了（注意是边的数量而不是点的）。

最后套一个无聊的高精度板子就ok了，因为格式错误wa了几次。。。UVALive貌似经常有把格式错误当成wa的。。。顺便这个对高精度的要求还挺高，1000位都满足不了开了100000位才过，至于吗呵呵

继续阅读“[图论][双联通分量][无向图仙人掌] UVALive 3514 Cactus”