离线版

首先将询问和加边一起排个序

对每个节点建一棵主席树，连边时主席树合并即可

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            using namespace std;typedef long long ll;const int maxn = 1000010;int n,m,q;int a[maxn],b[maxn],fa[maxn],rt[maxn],ans[maxn],p,tot;struct Node{ int sz,ls,rs;}t[maxn<<2];struct Q{ int a,b,c,ok,id;}c[maxn<<2];int find(int x){ return x==fa[x]?x:fa[x]=find(fa[x]); }bool cmp(Q a,Q b){ if(a.c==b.c) return a.ok
            
             '9'){ if(ch=='-') f=-1; ch=getchar(); } while(ch>='0' && ch<='9'){ s=s*10+ch-'0'; ch=getchar(); } return s*f;}int main(){ n=read(),m=read(),q=read(); for(int i=1;i<=n;i++) a[i]=read(),b[i]=a[i],fa[i]=i; sort(b+1,b+1+n); p=unique(b+1,b+1+n)-b-1; for(int i=1;i<=n;i++) a[i]=lower_bound(b+1,b+1+p,a[i])-b; for(int i=1;i<=m;i++) c[i].a=read(),c[i].b=read(),c[i].c=read(),c[i].ok=0; for(int i=m+1;i<=m+q;i++) c[i].a=read(),c[i].c=read(),c[i].b=read(),c[i].ok=1,c[i].id=i-m; sort(c+1,c+1+m+q,cmp); for(int i=1;i<=n;i++) modify(rt[i],1,p,a[i]); for(int i=1;i<=m+q;i++){ if(c[i].ok==0){ int u=find(c[i].a),v=find(c[i].b); if(u!=v){ fa[u]=v; rt[v]=merge(rt[u],rt[v]); } }else{ int u=find(c[i].a); if(t[rt[u]].sz