http://www.lydsy.com/JudgeOnline/problem.php?id=4537 (题目链接)
题意
给出一个${n}$个点${m}$条边的无向图，每条边有两个权值${a,b}$。给出$Q$个询问，问$u,v$两点间是否存在一条路径（可以不是简单路径），使得路径上的边的最大$a,b$正好等于$A,B$。
Solution
http://blog.csdn.net/zmh964685331/article/details/51194393
我们考虑按照$a$的权值分块。每次找到$a$的权值在块内的询问，对它们进行处理。
将这些询问按照$b$的大小排序以后，我们用并查集维护图的连通性。此时的边有两类，第一类就是在之前的块中的边，这些边的$a$肯定是小于询问的$a$的，我们将这些边按照$b$排序，然后依次加入。第二类就是在当前块中的边，这些边我们不好处理，直接暴for过去，如果它们的$a,b$都小于询问的$a,b$，就加入到图中，做完之后再将这些边暴力还原，因为只有$\sqrt{m}$条，所以不虚。
并查集按秩合并，同时维护连通块中$a,b$的最值。查询的时候就是判断是否$u,v$在同一连通块中，这个连通块$a,b$的最大值是否正好等于询问的$a,b$。
细节
块的大小，开大一点，不然会TLE。
如果大块大块相同的$a$，我们的询问会被重复不断的加入，这是很浪费的，所以我们对这种情况进行一些处理。
bzoj是有多慢，本机20s，交上去几乎要TLE。。。
代码
// bzoj4537
#include<algorithm>
#include<iostream>
#include<cstdlib>
#include<cstring>
#include<cstdio>
#include<cmath>
#define LL long long
#define inf (1ll<<30)
#define Pi acos(-1.0)
#define free(a) freopen(a".in","r",stdin),freopen(a".out","w",stdout);
using namespace std;
inline int gi() {
int x=0,f=1;char ch=getchar();
while (ch<'0' || ch>'9') {if (ch=='-') f=-1;ch=getchar();}
while (ch>='0' && ch<='9') {x=x*10+ch-'0';ch=getchar();}
return x*f;
}const int maxn=100010;
int ans[maxn],Q,n,m,top,tot,S;
int fa[maxn],da[maxn],db[maxn],size[maxn];
struct option {int u,v,da,db,fa,size;}op[maxn];
struct data {int u,v,a,b,id;}e[maxn],q[maxn],tmp[maxn];inline bool cmpa(data a,data b) {return a.a==b.a ? a.b<b.b : a.a<b.a;}
inline bool cmpb(data a,data b) {return a.b==b.b ? a.a<b.a : a.b<b.b;}inline int find(int x) {
return fa[x]==x ? x : find(fa[x]);
}
inline void Union(int u,int v,int a,int b) {
u=find(u),v=find(v);
if (size[u]>size[v]) swap(u,v);
op[++tot]=(option){u,v,da[v],db[v],fa[u],size[v]};
if (u==v) da[v]=max(da[v],a),db[v]=max(db[v],b);
else {
fa[u]=v;size[v]+=size[u];
da[v]=max(da[v],max(da[u],a));
db[v]=max(db[v],max(db[u],b));
}
}
int main() {
n=gi(),m=gi();
for (int i=1;i<=m;i++) e[i].u=gi(),e[i].v=gi(),e[i].a=gi(),e[i].b=gi(),e[i].id=i;
S=(int)sqrt(3*m);
Q=gi();
for (int i=1;i<=Q;i++) q[i].u=gi(),q[i].v=gi(),q[i].a=gi(),q[i].b=gi(),q[i].id=i;
sort(e+1,e+1+m,cmpa);
sort(q+1,q+1+Q,cmpb);
for (int i=1;i<=m;i+=S) {
int L=i,R=min(i+S-1,m);
top=0;
for (int j=1;j<=Q;j++)
if (q[j].a>=e[L].a && (R==m || q[j].a<e[R+1].a)) tmp[++top]=q[j]; //考虑很多边a相等的情况
sort(e+1,e+L,cmpb);
for (int j=1;j<=n;j++) fa[j]=j,size[j]=1,da[j]=db[j]=-1;
for (int j=1,k=1;j<=top;j++) {
for (;k<L && e[k].b<=tmp[j].b;k++) Union(e[k].u,e[k].v,e[k].a,e[k].b);
tot=0;
for (int l=L;l<=R;l++)
if (e[l].a<=tmp[j].a && e[l].b<=tmp[j].b) Union(e[l].u,e[l].v,e[l].a,e[l].b);
int u=find(tmp[j].u),v=find(tmp[j].v);
ans[tmp[j].id]= u==v && da[u]==tmp[j].a && db[u]==tmp[j].b;
for (;tot;tot--) {
fa[op[tot].u]=op[tot].fa;
db[op[tot].v]=op[tot].db;
da[op[tot].v]=op[tot].da;
size[op[tot].v]=op[tot].size;
}
}
}
for (int i=1;i<=Q;i++) printf(ans[i] ? "Yes\n" : "No\n");
return 0;
}
