问题描述
给定一张个顶点
条边的无向图(顶点编号为
),每条边上带有权值。所有权值都可以分解成
的形式。
现在有 个询问,每次询问给定四个参数和
,请你求出是否存在一条顶点
到
之间的路径,使得路径依次经过的边上的权值的最小公倍数为
。
注意:路径可以不是简单路径。
注意到不一定是简单路径,所以我们看联通性即可
也就是说,我们找到所有的边,用并查集合并,看
是否联通以及
是否恰好等于
考虑对边分块
我们将边按排序,询问按
排序
每一个询问找到最后一个小于它的
的边,加入那个块
我们处理第块内的询问
首先,对于前块的边,我们可以保证它们的
第
块所有询问的
那么我们就对前面的边按再排序一次
然后,处理第块每个询问,由于询问的
有序,所以以前加入的边可以不用删除,原基础上直接加
但是第块内
无序
所有我们暴力枚举第块的边加入
但这部分要撤销
可撤销并查集即可
时间复杂度
#include <bits/stdc++.h> #define ri register int #define ll long long using namespace std; const int Maxn=5e4; const int Maxm=1e5; const int Maxk=350; struct Edge { int x,y,a,b; }e[Maxm+5]; struct Query { int x,y,a,b,id; }q[Maxn+5]; vector<Query>v[Maxk+5]; int l[Maxk+5],r[Maxk+5],bel[Maxm+5],t[Maxm+5],ans[Maxn+5],n,m,Q; static char buf[30000000],*p1=buf,*p2=buf,obuf[30000000],*p3=obuf; #define getchar() p1==p2&&(p2=(p1=buf)+fread(buf,1,1000000,stdin),p1==p2)?EOF:*p1++ #define putchar(x) (p3-obuf<1000000)?(*p3++=x):(fwrite(obuf,p3-obuf,1,stdout),p3=obuf,*p3++=x) template<typename item> inline void read(register item &x) { x=0;register char c=getchar(); while(c<'0'||c>'9')c=getchar(); while(c>='0'&&c<='9')x=(x<<3)+(x<<1)+(c^48),c=getchar(); } inline int mymax(int x,int y) {return x>y?x:y;} struct UnionSet { Edge s[Maxm+5]; int father[Maxn+5],size[Maxn+5],mx_a[Maxn+5],mx_b[Maxn+5],top; inline void init() { for(ri i=1;i<=n;i++) { father[i]=i,size[i]=1; mx_a[i]=mx_b[i]=-1; } } inline int getfather(int v) { return father[v]==v?v:getfather(father[v]); } inline void merge(Edge t) { int fx=getfather(t.x),fy=getfather(t.y); if(size[fx]<size[fy])swap(fx,fy); s[++top]=(Edge){fx,fy,mx_a[fx],mx_b[fx]}; mx_a[fx]=mymax(mx_a[fx],t.a); mx_b[fx]=mymax(mx_b[fx],t.b); if(fx!=fy) { father[fy]=fx,size[fx]+=size[fy]; mx_a[fx]=mymax(mx_a[fx],mx_a[fy]); mx_b[fx]=mymax(mx_b[fx],mx_b[fy]); } } inline void del() { while(top) { Edge t=s[top--]; if(t.x!=t.y)size[t.x]-=size[t.y]; father[t.y]=t.y; mx_a[t.x]=t.a,mx_b[t.x]=t.b; } } }us; inline bool cmp1(Edge a,Edge b) { return a.a<b.a; } inline bool cmp2(Query a,Query b) { return a.b<b.b; } inline bool cmp3(Edge a,Edge b) { return a.b<b.b; } int main() { read(n),read(m); for(ri i=1;i<=Maxk;i++)l[i]=(i-1)*Maxk+1,r[i]=min(m,i*Maxk); for(ri i=1;i<=m;i++) { read(e[i].x),read(e[i].y),read(e[i].a),read(e[i].b); bel[i]=(i-1)/Maxk+1; } sort(e+1,e+m+1,cmp1); for(ri i=1;i<=m;i++)t[i]=e[i].a; read(Q); for(ri i=1;i<=Q;i++) { read(q[i].x),read(q[i].y),read(q[i].a),read(q[i].b); q[i].id=i; } sort(q+1,q+Q+1,cmp2); for(ri i=1;i<=Q;i++) { int x=upper_bound(t+1,t+m+1,q[i].a)-t-1; v[bel[x]].push_back(q[i]); } for(ri i=1;i<=bel[m];i++) { us.init(); sort(e+1,e+l[i],cmp3); int now=1; for(ri j=0;j<(int)v[i].size();j++) { Query t=v[i][j]; while(now<l[i]&&e[now].b<=t.b) { us.merge(e[now]); ++now; } us.top=0; for(ri k=l[i];k<=r[i]&&e[k].a<=t.a;k++) if(e[k].b<=t.b)us.merge(e[k]); int fx=us.getfather(t.x),fy=us.getfather(t.y); if(fx==fy&&us.mx_a[fx]==t.a&&us.mx_b[fx]==t.b)ans[t.id]=1; us.del(); } } for(ri i=1;i<=Q;i++) { if(ans[i])putchar('Y'),putchar('e'),putchar('s'); else putchar('N'),putchar('o'); putchar('\n'); } fwrite(obuf,p3-obuf,1,stdout); return 0; }