思路：

考虑按时间分治，然后把每条边按影响时间加入相应的区间(类似划分树)。然后考虑把包含每个叶子节点的边连起来，并判断有没有奇环。

由于分治时需要撤回某些并查集的合并操作，所以需要用到可撤销并查集。然后因为要判基环，所以又需要维护每个点到父亲节点的距离\(dp[i]\)，

所以需要用到带权并查集。

代码：

#pragma GCC optimize(2)#pragma GCC optimize(3)#pragma GCC optimize(4)#include
    
     using namespace std;#define y1 y11#define fi first#define se second#define pi acos(-1.0)#define LL long long#define mp make_pair#define pb push_back#define ls rt<<1, l, m#define rs rt<<1|1, m+1, r#define ULL unsigned LL#define pll pair
     
      #define pli pair
      
       #define pii pair
       
        #define piii pair
        
         #define pdd pair
         
          #define mem(a, b) memset(a, b, sizeof(a))#define debug(x) cerr << #x << " = " << x << "\n";#define fio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);//head const int N = 1e5 + 5;int n, m, T, u, v, l, r;vector
          
            vc[N<<2];bool ans[N];struct UFS { stack
           
            
              > stk; int fa[N], rnk[N], dp[N], c; inline void init(int n) { for (int i = 0; i <= n; ++i) fa[i] = i, rnk[i] = 0, dp[i] = 0; c = 0; } inline int Find(int x) { while(x^fa[x]) x = fa[x]; return x; } inline int Deep(int x) { int res = 0; while(x^fa[x]) res += dp[x], x = fa[x]; return res; } inline void Merge(int x, int y) { int fx = Find(x), fy = Find(y); if(fx == fy) { int dx = Deep(x), dy = Deep(y); if((dx+dy+1)%2) { stk.push(mp(&c, c)); c++; } return ; } if(rnk[fx] <= rnk[fy]) { stk.push(mp(fa+fx, fa[fx])); stk.push(mp(dp+fx, dp[fx])); dp[fx] = dp[y]-dp[x]+1; fa[fx] = fy; if(rnk[fx] == rnk[fy]) { stk.push(mp(rnk+fy, rnk[fy])); rnk[fy]++; } } else { stk.push(mp(fa+fy, fa[fy])); stk.push(mp(dp+fy, dp[fy])); dp[fy] = dp[x]-dp[y]+1; fa[fy] = fx; } } inline void Undo() { *stk.top().fi = stk.top().se; stk.pop(); }}ufs;void update(int L, int R, pii p, int rt, int l, int r) { if(L <= l && r <= R) return vc[rt].pb(p), void(); int m = (l+r) >> 1; if(L <= m)update(L, R, p, ls); if(R > m) update(L, R, p, rs);}void dfs(int rt, int l, int r) { for (int i = 0; i < vc[rt].size();++i) ufs.Merge(vc[rt][i].fi, vc[rt][i].se); if(l == r) { if(ufs.c) printf("No\n"); else printf("Yes\n"); return ; } int sz = ufs.stk.size(); int m = (l+r) >> 1; dfs(ls); while(ufs.stk.size() > sz) ufs.Undo(); dfs(rs); while(ufs.stk.size() > sz) ufs.Undo();}int main() { scanf("%d %d %d", &n, &m, &T); for (int i = 1; i <= m; ++i) scanf("%d %d %d %d", &u, &v, &l, &r), update(l+1, r, {u, v}, 1, 1, T); ufs.init(n); dfs(1, 1, T); return 0;}