bzoj 4129: Haruna's Breakfast

.

题意：在一棵n个节点的树上修改一个节点的值或求一条链上所以节点的mex
题解：树上带修改莫队
直接上。不解释。
代码：

#include<bits/stdc++.h>
using namespace std;

int n,m,num=0,fst[50010],a[50010],nn=0,blocksize,tn=0,qn=0,t=0,cnt[50010],blocksize2,size[250],last[50010],aa[50010];
struct edge
{
    int x,y,n;
}e[100010];
struct pnt
{
    int dep,f[17],id,block;
}p[50010];
struct query
{
    int x,y,id,t,ans;
}q[50010];
struct mod
{
    int x,y,last;
}d[50010];
bool in[50010];

void ins(int x,int y)
{
    e[++num]={x,y,fst[x]};
    fst[x]=num;
}
int cmp(query x,query y)
{
    return p[x.x].block==p[y.x].block?p[x.y].id<p[y.y].id:p[x.x].id<p[y.x].id;
}
void dfs(int x,int f)
{
    p[x].dep=p[f].dep+1;
    p[x].f[0]=f;
    for(int i=1;i<17;i++)
    p[x].f[i]=p[p[x].f[i-1]].f[i-1];
    p[x].id=++nn;
    p[x].block=p[x].id/blocksize;
    for(int i=fst[x];i;i=e[i].n)
    {
        int y=e[i].y;
        if(y==f)
        continue;
        dfs(y,x);
    }
}
int getlca(int x,int y)
{
    if(p[x].dep<p[y].dep)
    swap(x,y);
    for(int i=16;i>=0;i--)
    if((1<<i)<=p[x].dep-p[y].dep)
    x=p[x].f[i];
    if(x==y)
    return x;
    for(int i=16;i>=0;i--)
    if(p[x].f[i]!=p[y].f[i])
    {
        x=p[x].f[i];
        y=p[y].f[i];
    }
    return p[x].f[0];
}
void add(int x,int y)
{
    if(x>n)
    return;
    if(cnt[x]==0&&y==1)
    size[x/blocksize2]++;
    if(cnt[x]==1&&y==-1)
    size[x/blocksize2]--;
    cnt[x]+=y;
}
void chg(int x,int y)
{
    if(in[x])
    {
        add(a[x],-1);
        add(y,1);
    }
    a[x]=y;
}
int getans()
{
    for(int i=0;;i++)
    if(size[i]<blocksize2)
    {
        for(int j=i*blocksize2;;j++)
        if(!cnt[j])
        return j;
    }
}
void move(int x,int y)
{
    int lca=getlca(x,y);
    while(x!=lca)
    {
        if(in[x])
        add(a[x],-1);
        else
        add(a[x],1);
        in[x]^=1;
        x=p[x].f[0];
    }
    while(y!=lca)
    {
        if(in[y])
        add(a[y],-1);
        else
        add(a[y],1);
        in[y]^=1;
        y=p[y].f[0];
    }
}
int cmp2(query x,query y)
{
    return x.id<y.id;
}
int main()
{
    scanf("%d%d",&n,&m);
    blocksize=int(ceil(pow(n,2.0/3)));
    blocksize2=int(sqrt(n));
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&a[i]);
        aa[i]=a[i];
    }
    for(int i=1;i<n;i++)
    {
        int x,y;
        scanf("%d%d",&x,&y);
        ins(x,y);
        ins(y,x);
    }
    dfs(1,0);
    for(int i=0;i<m;i++)
    {
        int op,x,y;
        scanf("%d%d%d",&op,&x,&y);
        if(op==0)
        {
            d[++tn]={x,y,last[x]};
            last[x]=tn;
        }
        else
        {
            q[qn++]={x,y,i,tn,0};
        }
    }
    sort(q,q+qn,cmp);
    int x=1,y=1;
    for(int i=0;i<qn;i++)
    {
        while(t<q[i].t)
        {
            t++;
            chg(d[t].x,d[t].y);
        }
        while(t>q[i].t)
        {
            int last=d[t].last;
            if(last==0)
            chg(d[t].x,aa[d[t].x]);
            else
            chg(d[t].x,d[last].y);
            t--;
        }
        move(x,q[i].x);
        move(y,q[i].y);
        int lca=getlca(q[i].x,q[i].y);
        add(a[lca],1);
        q[i].ans=getans();
        add(a[lca],-1);
        x=q[i].x;
        y=q[i].y;
    }
    sort(q,q+qn,cmp2);
    for(int i=0;i<qn;i++)
    printf("%d\n",q[i].ans);
}