Description

神犇有一个n个节点的图。因为神犇是神犇,所以在T时间内一些边会出现后消失。神犇要求出每一时间段内这个图是否是二分图。这么简单的问题神犇当然会做了,于是他想考考你。

Input

输入数据的第一行是三个整数n,m,T。
第2行到第m+1行,每行4个整数u,v,start,end。第i+1行的四个整数表示第i条边连接u,v两个点,这条边在start时刻出现,在第end时刻消失。

Output

输出包含T行。在第i行中,如果第i时间段内这个图是二分图,那么输出“Yes”,否则输出“No”,不含引号。

Sample Input

3 3 3
1 2 0 2
2 3 0 3
1 3 1 2

Sample Output

Yes
No
Yes

HINT

样例说明:
0时刻,出现两条边1-2和2-3。
第1时间段内,这个图是二分图,输出Yes。
1时刻,出现一条边1-3。
第2时间段内,这个图不是二分图,输出No。
2时刻,1-2和1-3两条边消失。
第3时间段内,只有一条边2-3,这个图是二分图,输出Yes。
数据范围:
n<=100000,m<=200000,T<=100000,1<=u,v<=n,0<=start<=end<=T。
题意:略
二分图性质 不存在奇环的图
首先将所有边读入 按照开始出现的时间排序 按照出现的时间依次添加 那么我们可以知道 当我这个环上最早消失的那条边消失之后我的这个奇环也就不复存在了 那么不妨针对每个事件我开一个桶 存入这个时间一共有多少条这样的边 然后过了这个时间后就把这条边的影响消除掉即可 最后在回答询问的时候看一看全图是否还存在这样的奇边 根据这个情况回答即可 那相当于我需要维护一个以消失时间为权值的最大生成树 针对做每条边的时候 如果形成奇环 那么我就将这这条边消失时间插入桶内关于 边权如何用lct维护 参考noi2014魔法森林 将边权重新建一个新点判断是否是奇环 直接把这条链提取出来看一下size即可 一开始我以为find之后就不需要每次splay都要下放 其实仍然需要 注意判断自环的情况 更新的时候我们每次在链上找一个最小点 如果我这个边比最小边要大 那么就更新最小边

 

分类: LCT-link cut tree

elijahqi

辣鸡蒟蒻一枚qwq 欢迎加qq qwq 2922945330

发表评论