题意:链接方法: LCT解析:闲来无事随机了一道题，看完题后，我靠这上LCT不就能搞？随机都能随机个LCT，简直。然后就快快乐乐地写了个维护删除时间的最大生成树。WA..噢难道没这么水！一定我想少了。等等二分图是啥玩意来着。 二分图又称作二部图，是图论中的一种特殊模型。 设G=(V,E)是一个无向图，如果顶点V可分割为两个互不相交的子集(A,B)，并且图中的每条边（i，j）所关联的两个顶点i和j分别属于这两个不同的顶点集(i in A,j in B)，则称图G为一个二分图。等等也就是这玩意可以有环？woc画风不对啊，赶紧百度一些关于二分图的东西。然后看到没有奇环这个定义？奇环是啥？我只知道基环树啊。然后宋爷告诉我:奇环不就是有奇数个点的环么….对啊！=-=智商下线。既然二分图不能有奇环，这是显然的嘛！就是从另一个集合跑这个环总会连会自己的集合，，这显然不是二分图么。那维护就得多一项咯？连边的时候，如果这是自环，显然不行，扔到一个数组里，代表这边存在的时候不能是二分图。如果不产生环，直接连。如果产生环先看这个边的删除时间是否要我们添到树里，如果删除时间较环上删除时间最小的边要小，那么看产生的是奇环还是偶环，奇环则扔到数组里。如果比环上删除时间最小的边要大，则判断下是奇环还是偶环，奇环则把原来的边扔到数组里，接着就D原来的边连上新的边。删除边的话，就看这个边在哪里，如果在树上直接删，不影响答案，如果在数组里就把它扔辣就行辣。枚举每个时间的时候，把这个时间的操作都做完后，看目前的那个数组是否为空，如果为空则为二分图，不为空则不是二分图。然而这题可以用分治加并查集？挖坑。代码:M 200010#define N 300010using namespace std;int n,m,t;struct node{int x,y,a,b,deltag,no; }l[M],l2[M];int fa[N],ch[N][2],mn[N],val[N],rt[N],rev[N],siz[N];void pushup(int x){if(!x)return;mn[x]=x;siz[x]=x>n;if(ch[x][0]!=0&&val[mn[x]]>val[mn[ch[x][0]]])mn[x]=mn[ch[x][0]];if(ch[x][1]!=0&&val[mn[x]]>val[mn[ch[x][1]]])mn[x]=mn[ch[x][1]];if(ch[x][0]!=0)siz[x]+=siz[ch[x][0]];if(ch[x][1]!=0)siz[x]+=siz[ch[x][1]];}void reverse(int x){if(!x)return ;swap(ch[x][0],ch[x][1]);rev[x]^=1;}void pushdown(int x){if(!x)return;if(rev[x]){reverse(ch[x][0]),reverse(ch[x][1]);rev[x]=0;}}void down(int x){if(!rt[x])down(fa[x]);pushdown(x);}void rotate(int x){int y=fa[x],kind=ch[y][1]==x;ch[y][kind]=ch[x][!kind];fa[ch[y][kind]]=y;ch[x][!kind]=y;fa[x]=fa[y];fa[y]=x;if(rt[y])rt[y]=0,rt[x]=1;else ch[fa[x]][ch[fa[x]][1]==y]=x;pushup(y);}void splay(int x){down(x);while(!rt[x]){int y=fa[x],z=fa[y];if(rt[y])rotate(x);else if((ch[y][1]==x)==(ch[z][1]==y))rotate(y),rotate(x);else rotate(x),rotate(x);}pushup(x); }void access(int x){int y=0;while(x){splay(x);rt[ch[x][1]]=1,rt[y]=0;ch[x][1]=y;pushup(x);y=x,x=fa[x];}}void movetoroot(int x){access(x);splay(x);reverse(x);}void link(int x,int y){movetoroot(x);fa[x]=y;}void cut(int x,int y){movetoroot(x);access(y);splay(y);ch[y][0]=0;fa[x]=0;rt[x]=1; }int find_root(int x){access(x),splay(x);while(ch[x][0])x=ch[x][0];return x;}int head[N],head2[N];struct node2{int from,to,next;}edgead[N],edgede[N];int cnt,cnt2;void init(){memset(head,-1,sizeof(head));memset(head2,-1,sizeof(head2));cnt=cnt2=1; }void edgeadd(int from,int to){edgead[cnt].from=from,edgead[cnt].to=to;edgead[cnt].next=head[from];head[from]=cnt++;} void edgeadd2(int from,int to){edgede[cnt2].from=from,edgede[cnt2].to=to;edgede[cnt2].next=head2[from];head2[from]=cnt2++; }int onthetree[N],inthearr[N];int intotal;int main(){scanf(“%d%d%d”,&n,&m,&t);init();memset(val,0x3f,sizeof(val));for(int i=1;i<=m;i++){scanf(“%d%d%d%d”,&l[i].x,&l[i].y,&l[i].a,&l[i].b);edgeadd(l[i].a,i),edgeadd2(l[i].b,i);val[i+n]=l[i].b,mn[i+n]=i+n;}for(int i=1;i<=n;i++)rt[i]=1;for(int i=1;i<=m;i++)rt[i+n]=1,siz[i+n]=1;for(int T=0;T<t;T++){for(int i=head[T];i!=-1;i=edgead[i].next){int to=edgead[i].to;int x=l[to].x,y=l[to].y;if(x==y)inthearr[to]=1,intotal++;else if(find_root(x)!=find_root(y)){onthetree[to]=1,link(x,to+n),link(to+n,y);}else{movetoroot(x),access(y),splay(y);int tmp=mn[y]-n;if(l[tmp].b<l[to].b){if(!(siz[y]&1))inthearr[tmp]=1,intotal++;cut(l[tmp].x,tmp+n),cut(tmp+n,l[tmp].y);link(x,to+n),link(to+n,y);onthetree[tmp]=0,onthetree[to]=1;}else if(!(siz[y]&1))inthearr[to]=1,intotal++;}}for(int i=head2[T];i!=-1;i=edgede[i].next){int to=edgede[i].to;if(onthetree[to]){cut(l[to].x,to+n),cut(to+n,l[to].y);}else if(inthearr[to])intotal–;}if(intotal)puts(“No”);else puts(“Yes”);}}
你可以用爱得到全世界，你也可以用恨失去全世界
