E. Qpwoeirut and Vertices

思路:
1.克鲁斯卡尔重构树,重构以后可以发现从任意两点可达的最大边序号就是重构树多点LCA的点权.
2.用ST表维护区间DFS序最大值和最小值.
3.多点LCA结论:

AC Code:

#include<bits/stdc++.h>
#pragma optimize(2)
#define endl '\n'
#define ll() to_ullong() 
#define string() to_string()
#define Endl endl
using namespace std;
typedef long long ll;
typedef pair<int,int>PII; 
typedef unsigned long long ull;
const int M=2010;
const int P=13331;
const ll  llinf=0x3f3f3f3f3f3f3f3f;
const int inf=0x3f3f3f3f;
const int mod=1e9+7;
const int N=4e5+10;
int dx[4]={0,1,0,-1};
int dy[4]={-1,0,1,0};
int e[N],ne[N],idx,h[N],w[N];
int n,m,q,dep[N],cnt,fa[N][64],p[N];
int dfn[N],maxv[N][32],minv[N][32],id[N],num,root;
void add(int a,int b)
{
        e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}
int find(int x)
{
        return p[x]==x?x:p[x]=find(p[x]);
}
void init()
{

     for(int j=0;j<=(int)log2(n);j++)
      for(int i=1;i+(1<<j)-1<=n;i++)
       if(!j)maxv[i][j]=dfn[i];
       else maxv[i][j]=max(maxv[i][j-1],maxv[i+(1<<(j-1))][j-1]);

     for(int j=0;j<=(int)log2(n);j++)
      for(int i=1;i+(1<<j)-1<=n;i++)
       if(!j)minv[i][j]=dfn[i];
       else minv[i][j]=min(minv[i][j-1],minv[i+(1<<(j-1))][j-1]);
}
struct Edge{
        int u,v,val;
        bool operator <(const Edge &a)const
        {
                return val<a.val;
        }
}edge[N];
void ex_kruskal()
{
        sort(edge+1,edge+1+m);
        num=n,root=0,cnt=0;
        for(int i=1;i<=2*n;i++)p[i]=i,h[i]=-1,w[i]=0;

        for(int i=1;i<=m;i++)
        {
                int x=find(edge[i].u),y=find(edge[i].v);
                if(x!=y)
                {
                        p[x]=p[y]=++num;
                        root=max(root,num);
                        w[num]=edge[i].val;
                        add(num,x),add(x,num);
                        add(num,y),add(y,num);
                }
        }
}
void dfs(int u,int father,int depth)
{
        dep[u]=depth,dfn[u]=++cnt,id[dfn[u]]=u;

        if(u!=root)
        {
                fa[u][0]=father;
                for(int k=1;k<=32;k++)fa[u][k]=fa[fa[u][k-1]][k-1];
        }

        for(int i=h[u];~i;i=ne[i])
        {
                int j=e[i];
                if(j==father)continue;
                dfs(j,u,depth+1);
        }
}
int lca(int x,int y)
{
        if(dep[x]<dep[y])swap(x,y);

        for(int i=32;i>=0;i--)
         if(dep[fa[x][i]]>=dep[y])x=fa[x][i];

        if(x==y)return x;

        for(int i=32;i>=0;i--)
         if(fa[x][i]!=fa[y][i])x=fa[x][i],y=fa[y][i];

        return fa[x][0];
}
void solve()
{
       cin>>n>>m>>q;

       for(int i=1;i<=m;i++)
       {
               int u,v;
               cin>>u>>v;
               edge[i]={u,v,i};
       }
       ex_kruskal();
       dfs(root,-1,1);
       init();//维护区间 Dfs 的最大值和最小值 
       while(q--)
       {
               int l,r;
               cin>>l>>r;//
               int len=(int)log2(r-l+1); 
               int Max=max(maxv[l][len],maxv[r-(1<<len)+1][len]);
               int Min=min(minv[l][len],minv[r-(1<<len)+1][len]);

               int anc=lca(id[Min],id[Max]);
               cout<<w[anc]<<' ';
       }
       cout<<endl;
       return ;
}
int main()
{
        ios_base::sync_with_stdio(0);
        cin.tie(0);
        cout.tie(0);
     //   freopen("test.in","r",stdin);
        int t;cin>>t;
        while(t--)solve();
        return 0;
}

克鲁斯卡尔重构树 模板:

struct Edge{
        int u,v,val;
        bool operator <(const Edge &a)const
        {
                return val<a.val;
        }
}edge[N];
void ex_kruskal()
{
        sort(edge+1,edge+1+m);
        num=n,root=0,cnt=0;
        for(int i=1;i<=2*n;i++)p[i]=i,h[i]=-1,w[i]=0;

        for(int i=1;i<=m;i++)
        {
                int x=find(edge[i].u),y=find(edge[i].v);
                if(x!=y)
                {
                        p[x]=p[y]=++num;
                        root=max(root,num);
                        w[num]=edge[i].val;
                        add(num,x),add(x,num);
                        add(num,y),add(y,num);
                }
        }
}