Description：

给定一张 $N$ 个顶点 $M$ 条边的无向图，每条边上带有权值。所有权值都可以分解成 $2^a\times3^b$ 的形式。

现在有 $Q$ 个询问，每次询问给定四个参数 $u,v,a$ 和 $b$ ，请你求出是否存在一条顶点 $u$ 到 $v$ 之间的路径，使得路径依次经过的边上的权值的最小公倍数为 $2^a\times3^b$ 。路径可以不是简单路径。

$1\le n,q\le50000$ $1\le m \le100000$

Solution：

转化一下就是问是否存在求一条路径使得 $a$ 的最大值和 $b$ 的最大值分别为给定的值。既然可以不是简单路径，那么只要 $u$ 和 $v$ 所在联通块内有 $a$ 和 $b$ 的最大值即可，不难想到一个 $O(mq)$ 的做法，对于每个询问将所有 $a\le qa$ 且 $b\le qb$ 的边加进去判断能否联通即可，但会超时。

$50000$ 的数据范围大概率就是根号算法了，先将所有边按 $a$ 分块，每次将属于这个块的所有询问找出来，将这个块之前的边和询问都按 $b$ 排序，然后 $two\ pointer$ 扫一下即可。

但发现在当前这个块中 $a$ 不一定都满足条件，但只有块大小个，于是用不带路径压缩的可撤销的并查集维护，每次将一个询问能加的边加进去，退出时暴力将属于这个块的边全部撤销即可，注意所有修改都要压入栈中回收，即使只是 $max$ 值改变而连接情况没有变也要回收。可以将这个块之前的边先处理，处理到块内边时记一下栈高，然后加这个块中的边，退出时弹到原栈高即可，注意每次要清空撤回栈。

有必要分析一下他的时间复杂度：

每个询问只会处理一次 $O(N)$ ，每次询问会暴枚所有当前块内的边 $O(N\times siz)$

共有 $M/siz$ 个块，每个块中会枚举所有边并排序 $O(Mlog_2M)$ 。

于是答案是 $O(N\times siz+\frac M {siz}Mlog_2M)$

由均值不等式得当 $siz=\sqrt {Mlog_2M}$ 时最快，为 $O(N\sqrt {Mlog_2M})$

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cstring>

using namespace std;

int n,m;

#define MAXN 50010

#define MAXM 100010

struct edge

{

	int u,v,a,b,s;

}e[MAXM];

int t;

struct query

{

	int u,v,a,b,ans,id;

	query(){ans = 0;}

}q[MAXN];

namespace UFS

{

	int f[MAXN],siz[MAXN],maxa[MAXN],maxb[MAXN];

	int find(int x){return (x == f[x] ? x : find(f[x]));}

	edge stack[MAXN << 4];

	int top = 0;

	inline void merge(edge k)

	{//cout << "add " << k.u << " " << k.v << " " << k.a << " " << k.b << endl; 

		int x = k.u;int y = k.v;

		x = find(x);y = find(y);

		if(x == y)

		{

			stack[++top] = (edge){x,y,maxa[y],maxb[y],siz[y]}; 

			maxa[y] = max(maxa[y],k.a);

			maxb[y] = max(maxb[y],k.b);

			return;

		}

		if(siz[x] > siz[y])swap(x,y);

		stack[++top] = (edge){x,y,maxa[y],maxb[y],siz[y]};

		f[x] = y;siz[y] += siz[x];

		maxa[y] = max(maxa[x],maxa[y]);

		maxb[y] = max(maxb[x],maxb[y]);

		maxa[y] = max(maxa[y],k.a);

		maxb[y] = max(maxb[y],k.b);

		return;

	}

	inline void reset(int bottom)

	{

		while(top > bottom)

		{

			int x = stack[top].u,y = stack[top].v;//cout << "del " << x << " " << y << " " << stack[top].a << " " << stack[top].b << endl;

			f[x] = x;

			maxa[y] = stack[top].a;maxb[y] = stack[top].b;

			siz[y] = stack[top].s;

			--top;

		}

		return;

	}

}

bool cmp_e_a(edge x,edge y){return x.a < y.a;}

bool cmp_e_b(edge x,edge y){return x.b < y.b;}

int L[MAXN],R[MAXN],tot = 0,siz;

void build(int l,int r,int k){L[k] = l;R[k] = r;return;}

bool cmp_q_b(query x,query y){return x.b < y.b;}

int qs[MAXN];

int curq = 0;

bool cmp_q_id(query a,query b){return a.id < b.id;}

inline int read()

{

	register int res = 0;

	register char c = getchar();

	while(!isdigit(c))c = getchar();

	while(isdigit(c))

	{

		res = (res << 1) + (res << 3) + c - '0';

		c = getchar();

	}

	return res;

}

int main()

{

	n = read();m = read();

	for(int i = 1;i <= m;++i)

	{

		e[i].u = read();e[i].v = read();e[i].a = read();e[i].b = read();

	}

	t = read();

	for(int i = 1;i <= t;++i)

	{

		q[i].u = read();q[i].v = read();q[i].a = read();q[i].b = read();

	}

	for(int i = 1;i <= t;++i)q[i].id = i;

	sort(e + 1,e + 1 + m,cmp_e_a);

	sort(q + 1,q + 1 + t,cmp_q_b);

	siz = sqrt(m * log2(n));tot = m / siz;

	for(int i = 1;i <= tot;++i)build((i - 1) * siz + 1,i * siz,i);

	if(tot * siz < m){build(R[tot] + 1,m,tot + 1);++tot;}

	for(int k = 1;k <= tot;++k)

	{//cout << "new block " << L[k] << " " << R[k] << endl;

		curq = 0;

		for(int i = 1;i <= t;++i)

			if(e[L[k]].a <= q[i].a && (k == tot || q[i].a < e[L[k + 1]].a))

				qs[++curq] = i;

		for(int i = 1;i <= n;++i)

		{

			UFS::f[i] = i;UFS::siz[i] = 1;

			UFS::maxa[i] = UFS::maxb[i] = -1;

		}

		UFS::top = 0; 

		sort(e + 1,e + L[k],cmp_e_b);

		for(int pe = 0,pq = 1;pq <= curq;++pq)

		{

			for(;pe + 1 < L[k] && e[pe + 1].b <= q[qs[pq]].b;++pe)

				UFS::merge(e[pe + 1]);

			int bottom = UFS::top;

			for(int j = L[k];j <= R[k];++j)

				if(e[j].a <= q[qs[pq]].a && e[j].b <= q[qs[pq]].b)

					UFS::merge(e[j]);

			int x = UFS::find(q[qs[pq]].u),y = UFS::find(q[qs[pq]].v);//cout << UFS::maxa[x] << " - " << UFS::maxb[x] << endl;

			q[qs[pq]].ans = (x == y && UFS::maxa[x] == q[qs[pq]].a && UFS::maxb[x] == q[qs[pq]].b);

			UFS::reset(bottom);//cout << q[qs[pq]].ans << endl;

		}

	}

	sort(q + 1,q + 1 + t,cmp_q_id);

	for(int i = 1;i <= t;++i)

	{

		if(q[i].ans)puts("Yes");

		else puts("No");

	}

	return 0;

}