Description
给定一张N个顶点M条边的无向图(顶点编号为1,2,…,n)，每条边上带有权值。所有权值都可以分解成2^a*3^b
的形式。现在有q个询问，每次询问给定四个参数u、v、a和b，请你求出是否存在一条顶点u到v之间的路径，使得
路径依次经过的边上的权值的最小公倍数为2^a*3^b。注意：路径可以不是简单路径。下面是一些可能有用的定义
：最小公倍数：K个数a1,a2,…,ak的最小公倍数是能被每个ai整除的最小正整数。路径：路径P:P1,P2,…,Pk是顶
点序列，满足对于任意1<=i<k，节点Pi和Pi+1之间都有边相连。简单路径：如果路径P:P1,P2,…,Pk中，对于任意1
<=s≠t<=k都有Ps≠Pt，那么称路径为简单路径。
Input
输入文件的第一行包含两个整数N和M，分别代表图的顶点数和边数。接下来M行，每行包含四个整数u、v、a、
b代表一条顶点u和v之间、权值为2^a*3^b的边。接下来一行包含一个整数q，代表询问数。接下来q行，每行包含四
个整数u、v、a和b，代表一次询问。询问内容请参见问题描述。1<=n,q<=50000、1<=m<=100000、0<=a,b<=10^9
Output
对于每次询问，如果存在满足条件的路径，则输出一行Yes，否则输出一行 No（注意：第一个字母大写，其余
字母小写） 。
Sample Input
1 2 1 3
1 3 1 2
1 4 2 1
2 4 3 2
3 4 2 2
5
1 4 3 3
4 2 2 3
1 3 2 2
2 3 2 2
1 3 4 4
Sample Output
Yes
Yes
No
No
void merge(int x,int y,int a,int b)
{
int X=find(x),Y=find(y);
if(size[X]>size[Y]) swap(X,Y);
if(X==Y){maxa[Y]=max(maxa[Y],a),maxb[Y]=max(maxb[Y],b);return;}
fa[X]=Y;size[Y]+=size[X];
maxa[Y]=max(maxa[Y],max(a,maxa[X]));
maxb[Y]=max(maxb[Y],max(b,maxb[X]));
}
怎么暴力怎么来。。。
考虑到这种涉及两个权值的问题一般都要限制住一个条件
这题用在线算法是做不了的，貌似在线的话就只能对每个询问暴力搞了吧。。。
因为这种做法的缺陷在于它每次都要对所有的边进行处理,即必须对每个询问都重新构图，暴力判断。。。
那么我们考虑离线做法吧。。。
这题的思想极其巧妙，把边按照a的权值分块，询问按照b的权值排序！！！
-----真的不知道怎么想出来的。
直接说做法吧。。。
1.对于每个块，把满足这个块的A的条件的询问找出来。。。
2.我们对于这些满足的询问分两种情况来考虑目前对该询问的贡献：这个块之前的边(整块)，这个块目前的边(非整块);
3.对于第一种情况,那么对于这些询问来说，这个块以前的块中的边是一定A的条件的！！！(因为是按照a从小到大排序了的)
4.也就是说这些这些边只要满足b的条件即可,那么可以把这些边按bsort。
5.再把这些边只需按照满足b的条件依次加入即可。。。注意这些加入的边对于以后的询问也是会用到的，因为询问的边的b是递增的,所以每次不需重构图。
6.对于第二种情况，这些边的a和b都需要满足条件。。
7.并且由于满足这个块的询问的a并不一定是升序的，所以可能对于满足的两个询问i,j；
bi<bj,但ai>aj;这样就会有一个尴尬的问题，一条边的ax可能满足aj<ax<ai;显然这一条边在处理j的时候是不能算的，所以我们需要我们的并查集拥有回溯功能，即把刚刚加入 的边删掉；利用栈把每次加边之前的状态全部记录下来即可，加完后在回溯。
8.第一遍WA了，有点醉。。。
for(int i=;i<=q;i++)
{
if(ans[i]) puts("YES");
else puts("NO");
}
具体实现如下：
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
using namespace std;
const int N=;
int gi()
{
int x=;
char ch=getchar();
while(ch<''||ch>'') ch=getchar();
while(ch>=''&&ch<='') x=x*+ch-'',ch=getchar();
return x;
}
struct ac
{
int x,y,a,b,id;
}edge[N],query[N];
int n,m,q,block,pos[N],l[N],r[N],cnt,canuse[N],tt;
int fa[N],maxa[N],maxb[N],size[N],ans[N];
struct AC
{
int x,y,f,ma,mb,size;
}add[N];
bool cmpa(const ac &a,const ac &b)
{
if(a.a==b.a) return a.b<b.b;
return a.a<b.a;
}
bool cmpb(const ac &a,const ac &b)
{
if(a.b==b.b) return a.a<b.a;
return a.b<b.b;
}
int find(int x){return fa[x]==x?x:find(fa[x]);}
void merge(int x,int y,int a,int b)
{
int X=find(x),Y=find(y);
if(size[X]>size[Y]) swap(X,Y);
add[++tt]=(AC){X,Y,fa[X],maxa[Y],maxb[Y],size[Y]};
if(X==Y){maxa[Y]=max(maxa[Y],a),maxb[Y]=max(maxb[Y],b);return;}
fa[X]=Y;size[Y]+=size[X];
maxa[Y]=max(maxa[Y],max(a,maxa[X]));
maxb[Y]=max(maxb[Y],max(b,maxb[X]));
}
void del()
{
for(int i=tt;i>=;i--)
{
int x=add[i].x,y=add[i].y;
fa[x]=add[i].f;maxa[y]=add[i].ma;maxb[y]=add[i].mb;size[y]=add[i].size;
}
tt=;
}
int main()
{
n=gi(),m=gi();
for(int i=;i<=m;i++) edge[i].x=gi(),edge[i].y=gi(),edge[i].a=gi(),edge[i].b=gi();
q=gi();
for(int i=;i<=q;i++) query[i].x=gi(),query[i].y=gi(),query[i].a=gi(),query[i].b=gi(),query[i].id=i;
sort(edge+,edge++m,cmpa);
block=(int)sqrt(m);
sort(query+,query++q,cmpb);
for(int i=;i<=m;i+=block)
{
int tot=;
for(int j=;j<=q;j++)
if(query[j].a>=edge[i].a&&(query[j].a<edge[i+block].a||i+block>m))
canuse[++tot]=j;
sort(edge+,edge+i+,cmpb);
for(int j=;j<=n;j++) fa[j]=j,size[j]=,maxa[j]=-,maxb[j]=-;
int r=;
for(int j=;j<=tot;j++)
{
for(;r<i&&query[canuse[j]].b>=edge[r].b;r++) merge(edge[r].x,edge[r].y,edge[r].a,edge[r].b);
tt=;
for(int p=i;p<i+block&&p<=m;p++)
{
if(query[canuse[j]].b>=edge[p].b&&query[canuse[j]].a>=edge[p].a)
merge(edge[p].x,edge[p].y,edge[p].a,edge[p].b);
}
int x=find(query[canuse[j]].x),y=find(query[canuse[j]].y);
if(x==y&&maxa[x]==query[canuse[j]].a&&maxb[y]==query[canuse[j]].b) ans[query[canuse[j]].id]=;
else ans[query[canuse[j]].id]=;
del();
}
}
for(int i=;i<=q;i++)
{
if(ans[i]) puts("Yes");
else puts("No");
}
}