c小红的图上划分（牛客127）

题意：
有一个无向图，有 n 个点 m 条边，q 个询问，每次给出 L,R，求将图划分为至少 L 个连通块，最多 R个连通块的最大划分价值，若不可划分输出 "NO ANSWER"。
图的划分定义为将图划分为一个或多个连通块，对于每个连通块，其点集为其边集中每一条边的两端点的集合，且点集内任意两点均可通过边集里的边互相到达。
划分价值定义为所有连通块边集中的最小边权。

分析：先将边从大到小排序；用并查集，如果新增边的点没有共同祖先，连通块就减1，只要判断连通块<=r即可满足条件，不用管l的值，因为减少一个连通块，也就是多增一条边，这条边一定会小于原来的值的，答案要的是最大值，所有不用管。

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+10;
int f[N],ans[N];
struct A{
    int u,v,w;
}e[N];
int zx(int x){
    if(f[x]==x)return x;//x没爸爸
    else return f[x]=zx(f[x]);//找出爸爸的爸爸的。。 
}
void h(int x,int y){
    f[zx(y)]=zx(x);//x的最大祖先变成y最大祖先的爸爸； 
}
bool cmp(A x,A y){
    return x.w>y.w;
}
int main(){
    int n,m,q;cin>>n>>m>>q;
    for(int i=1;i<=m;i++)cin>>e[i].u>>e[i].v>>e[i].w;
    sort(e+1,e+m+1,cmp);
    for(int i=1;i<=n;i++)f[i]=i;
    int lt=n;
    for(int i=1;i<=m;i++){
        if(zx(e[i].u)!=zx(e[i].v)){
            h(e[i].u,e[i].v);
            lt--;
            ans[lt]=e[i].w;
        }
    }
    while(q--){
        int l,r;
        cin>>l>>r;
        if(r<lt)cout<<"NO ANSWER"<<endl;
        else cout<<ans[r]<<endl;
    }
    return 0;
}