Description

　　給定一張N個頂點M條邊的無向圖(頂點編號為1,2,…,n)，每條邊上帶有權(quán)值。所有權(quán)值都可以分解成2^a*3^b的形式?，F(xiàn)在有q個詢問，每次詢問給定四個參數(shù)u、v、a和b，請你求出是否存在一條頂點u到v之間的路徑，使得路徑依次經(jīng)過的邊上的權(quán)值的最小公倍數(shù)為2^a*3^b。注意：路徑可以不是簡單路徑。下面是一些可能有用的定義：最小公倍數(shù)：K個數(shù)a₁,a₂,…,a_k的最小公倍數(shù)是能被每個a_i整除的最小正整數(shù)。路徑：路徑P:P₁,P₂,…,P_k是頂點序列，滿足對于任意1<=i<k，節(jié)點P_i和P_i+1之間都有邊相連。簡單路徑：如果路徑P:P₁,P₂,…,P_k中，對于任意1<=s≠t<=k都有Ps≠Pt，那么稱路徑為簡單路徑。

Input

　　輸入文件的第一行包含兩個整數(shù)N和M，分別代表圖的頂點數(shù)和邊數(shù)。接下來M行，每行包含四個整數(shù)u、v、a、b代表一條頂點u和v之間、權(quán)值為2^a*3^b的邊。接下來一行包含一個整數(shù)q，代表詢問數(shù)。接下來q行，每行包含四個整數(shù)u、v、a和b，代表一次詢問。詢問內(nèi)容請參見問題描述。1<=n,q<=50000、1<=m<=100000、0<=a,b<=10^9

Output

　　對于每次詢問，如果存在滿足條件的路徑，則輸出一行Yes，否則輸出一行 No（注意：第一個字母大寫，其余字母小寫） 。

Sample Input

Sample Output

正解：神（gui）奇（chu）的分塊+并查集處理。

容易發(fā)現(xiàn)，此題就是要你求一條從u到v的路徑（不一定是簡單路徑），使得這條路徑上的maxa=給定a，maxb=給定b。

把所有邊按a排序，并分塊。把所有詢問按b排序。枚舉每一個塊，找出a的值在這個塊以內(nèi)的詢問。并直接把這個塊以前的所有邊按b排好序。首先，枚舉找出的每個詢問，并查集加入在這個塊以前的滿足條件的邊，然后再加入在這個塊中滿足條件的邊，最后查詢是否滿足條件。注意在當前塊中的邊需要在查詢完一個詢問以后撤回，因為這個塊中只滿足a單調(diào)，而詢問中只滿足b單調(diào)。所以這道題的并查集只能用啟發(fā)式合并，不能路徑壓縮。

//It is made by wfj_2048~#include <algorithm>#include <iostream>#include <cstring>#include <cstdlib>#include <cstdio>#include <vector>#include <cmath>#include <queue>#include <stack>#include <map>#include <set>#define inf (1<<30)#define il inline#define RG register#define ll long long#define File(s) freopen(s".in","r",stdin),freopen(s".out","w",stdout)using namespace std;struct data{ int u,v,a,b,i; }e[100010],q[100010],st[100010],update[100010];int ans[100010],fa[100010],size[100010],maxa[100010],maxb[100010],n,m,t,top,cnt,block;il int gi(){    RG int x=0,q=1; RG char ch=getchar(); while ((ch<'0' || ch>'9') && ch!='-') ch=getchar();    if (ch=='-') q=-1,ch=getchar(); while (ch>='0' && ch<='9') x=x*10+ch-48,ch=getchar(); return q*x;}il int cmpa(const data &x,const data &y){ return x.a<y.a || (x.a==y.a && x.b<y.b); }il int cmpb(const data &x,const data &y){ return x.b<y.b || (x.b==y.b && x.a<y.a); }il int find(RG int x){ return fa[x]==x ? x : find(fa[x]); }il void merge(RG int i){    RG int u=find(e[i].u),v=find(e[i].v); if (size[u]>size[v]) swap(u,v);    update[++cnt]=(data){u,v,maxa[v],maxb[v]}; if (u!=v) fa[u]=v,size[v]+=size[u];    maxa[v]=max(maxa[v],max(maxa[u],e[i].a)),maxb[v]=max(maxb[v],max(maxb[u],e[i].b)); return;}il void goback(){    for (RG int i=cnt;i;--i){	RG int u=update[i].u,v=update[i].v;	maxa[v]=update[i].a,maxb[v]=update[i].b;	if (u!=v) fa[u]=u,size[v]-=size[u];    }    return;}il void work(){    n=gi(),m=gi(); block=sqrt(m);    for (RG int i=1;i<=m;++i) e[i].u=gi(),e[i].v=gi(),e[i].a=gi(),e[i].b=gi(); sort(e+1,e+m+1,cmpa); t=gi();    for (RG int i=1;i<=t;++i) q[i].u=gi(),q[i].v=gi(),q[i].a=gi(),q[i].b=gi(),q[i].i=i; sort(q+1,q+t+1,cmpb);    for (RG int i=1;i<=m;i+=block){	top=0; for (RG int j=1;j<=t;++j) if (q[j].a>=e[i].a && (i+block>m || q[j].a<e[i+block].a)) st[++top]=q[j];	sort(e+1,e+i+1,cmpb); for (RG int j=1;j<=n;++j) maxa[j]=maxb[j]=-1,fa[j]=j,size[j]=1;	for (RG int j=1,k=1;j<=top;++j){	    for (;k<i && e[k].b<=st[j].b;++k) merge(k); cnt=0;	    for (RG int k=i;k<=m && k<i+block;++k) if (e[k].a<=st[j].a && e[k].b<=st[j].b) merge(k);	    RG int x=find(st[j].u),y=find(st[j].v); ans[st[j].i]=(x==y && maxa[x]==st[j].a && maxb[x]==st[j].b); goback();	}    }    for (RG int i=1;i<=t;++i) PRintf("%s/n",ans[i] ? "Yes" : "No"); return;}int main(){    File("multiple");    work();    return 0;}