G. Pandaria-技术圈

题意是有n个花园一个花园内所有的花的颜色都是一样的有很多种不同的颜色花园到花园之间有路，走不同的路有不同的代价
如果选一个点作为起点只走小于等于w的路可以经过的这些花园里那种颜色最多多组询问强制在线

解法对于这个影响这个答案有两个因素不可以把所有答案求出一个一个求的话复杂度太高因为强制在线所以我们需要先预处理一部分数据然后根据预处理的数据再进行求解答案，对于这个题面很明显可以想到先把边权最小的连起来然后是次最大然后再大点依次
明显就是一个求最小生成树的过程每次链接一条边的时候我们都可以从当前局面计算出一个答案明确可以知道存在一组询问的答案都是这个用并差集维护集合当我们把两个集合连接起来的时候就把这两个集合链接到一个点上用这个点来代码这个两个集合合并后的状态一共有n个点所以我们需要建立n-1个点按照最小生成树建树的顺序可以获得一个二叉树对于这个二叉树每一个节点都可以求一个答案这些答案可以回答所有询问，这些节点一共是 2n-1个（前n个几乎不用考虑就是本身）我们只需要先把这n-1个结点的答案预处理出来就可以了对于之后的询问我们就可以使用倍增直接找到从x点最高可以到的位置从而得出答案
对于那n-1的节点的答案维护要使用线段树合并（合并树最初的线段树要使用动态开点线段树动态开点的话也就是一共树就是一条链 log2e5 不会超过20个 n个线段树的话直接开个n*20的内存就可以了）

代码：

#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn = 2e5+7;
int color[maxn],f[maxn];
int find(int x){return f[x]==x?x:f[x]=find(f[x]);}
void init(int N){for(int i=1;i<=N;i++)f[i]=i;}
struct edge{int x,y,l;}E[maxn];
bool com(edge a,edge b){return a.l<b.l;}
struct Node{int l,r,mx;}node[maxn*20];
int N,M,tot,root[maxn];
void pushup(int rt){node[rt].mx=max(node[node[rt].l].mx,node[node[rt].r].mx);}
void bulit(int l,int r,int &rt,int pos)
{
    node[++tot]=(Node){0,0,0};rt=tot;
    if(l==r){node[rt].mx=1;return;}
    int m=(l+r)>>1;
    if(pos<=m)bulit(l,m,node[rt].l,pos);
    else bulit(m+1,r,node[rt].r,pos);
    pushup(rt);
}
void merge(int l,int r,int&x,int y)
{
    if(!x||!y){ x= x+y;return ;}
    if(l==r)node[x].mx+=node[y].mx;
    else{
        int m=(l+r)>>1;
        merge(l,m,node[x].l,node[y].l);
        merge(m+1,r,node[x].r,node[y].r);
        pushup(x);
    }
}
int ans[maxn],limt[maxn];
int getans(int l,int r,int x){
    if(l==r)return l;
    int m=(l+r)>>1;
    if(node[x].mx==node[node[x].l].mx)return getans(l,m,node[x].l);
    return getans(m+1,r,node[x].r);
}
int p[maxn][20];
int main()
{
    int T,cases=0,Q;
    scanf("%d",&T);
    while(T--)
    {
        memset(p,0,sizeof(p));
        scanf("%d%d",&N,&M);
        for(int i=1;i<=N;i++)scanf("%d",color+i);
        for(int i=0;i<M;i++)scanf("%d%d%d",&E[i].x,&E[i].y,&E[i].l);
        sort(E,E+M,com);
        init(N*2+1);tot=0;int cnt=N;
        for(int i=1;i<=N;i++)bulit(1,N,root[i],color[i]),ans[i]=color[i];
        for(int i=0;i<M;i++)
        {
            int x=find(E[i].x),y=find(E[i].y);
            if(x==y)continue;
            merge(1,N,root[x],root[y]);
            root[++cnt]=root[x];
            ans[cnt]=getans(1,N,root[x]);
            limt[cnt]=E[i].l;
            p[x][0]=p[y][0]=cnt;
            f[y]=f[x]=cnt;
        }
        for(int i=1;i<20;i++)
            for(int j=1;j<=cnt;j++)
                p[j][i]=p[p[j][i-1]][i-1];
        scanf("%d",&Q);
        printf("Case #%d:\n",++cases);
        int x,w,last=0;
        while(Q--){
            scanf("%d%d",&x,&w);
            x^=last;w^=last;
            for(int i=19;i>=0;i--)if(limt[p[x][i]]<=w&&p[x][i])x=p[x][i];
            printf("%d\n",last=ans[x]);
        }
    }
    return 0;
}