求助

一道并查集的题我偏是用了lct……

WA40，求指点

#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
const int maxn=500050;
int ch[maxn][2],par[maxn],rev[maxn],sum[maxn],val[maxn],sta[maxn];
int que[maxn],mark[maxn],ans[maxn],head[maxn],tot,len;
vector<int> vv[maxn];
struct edge
{
    int to,nxt,from;
}e[maxn];
void add(int x,int y)
{
    e[++tot].to=y;
    e[tot].nxt=head[x];
    e[tot].from=x;
    head[x]=tot;
}
bool chk(int x)
{
    return ch[par[x]][0]==x||ch[par[x]][1]==x;
}
void update(int x)
{
    sum[x]=sum[ch[x][0]]^sum[ch[x][1]]^val[x];
}
void reverse(int x)
{
    swap(ch[x][0],ch[x][1]);
    rev[x]^=1; 
}
void pushdown(int x)
{
    if (rev[x])
    {
        reverse(ch[x][0]);
        reverse(ch[x][1]);
        rev[x]=0;
    }
}
void rotate(int x)
{
    int y=par[x],z=par[y],k=(ch[y][1]==x),w=ch[x][k^1];
    if (chk(y)) ch[z][ch[z][1]==y]=x;
    ch[x][k^1]=y,ch[y][k]=w;
    if (w) par[w]=y;
    par[y]=x,par[x]=z;
    update(x),update(y);
}
void splay(int x)
{
    int y=x,z=0;
    sta[++z]=y;
    while (chk(y)) sta[++z]=y=par[y];
    while (z) pushdown(sta[z--]);
    while (chk(x))
    {
        y=par[x],z=par[y];
        if (chk(y)) rotate((ch[y][0]==x)^(ch[z][0]==y)?x:y);
        rotate(x);
    }
    update(x);
}
void access(int x)
{
    for (int y=0;x;x=par[y=x])
        splay(x),ch[x][1]=y,update(x);
}
void makeroot(int x)
{
    access(x),splay(x),reverse(x);
}
int findroot(int x)
{
    access(x),splay(x);
    while (ch[x][0]) pushdown(x),x=ch[x][0];
    return x;
}
void split(int x,int y)
{
    makeroot(x),access(y),splay(y);
}
void link(int x,int y)
{
    makeroot(x);
    if (findroot(y)!=x) par[x]=y;
}
void cut(int x,int y)
{
    split(x,y);
    if (findroot(y)==x&&par[x]==y&&!ch[x][1]) ch[y][0]=par[x]=0;
}
int n,m,x,y,ttt;
int main()
{
    scanf("%d%d",&n,&m);
    while (m--)
    {
        int x,y;
        scanf("%d%d",&x,&y);
        x++,y++;
        add(x,y);add(y,x);
    }
    int q;
    scanf("%d",&q);
    ttt=n-q;
    for (int i=1;i<=q;i++)
        scanf("%d",&que[i]),que[i]++,mark[que[i]]=1;
    for (int i=1;i<=2*m;i++)
    {
        if (!mark[e[i].from]&&!mark[e[i].to]&&findroot(e[i].from)!=findroot(e[i].to))
        {
            link(e[i].from,e[i].to);
            ttt--;
        }
    }
    ans[q+1]=ttt;
    for (int i=q;i>=1;i--)
    {
        int x=que[i];
        ttt++;
        mark[x]=false;
        for (int j=head[x];j;j=e[j].nxt)
        {
            int tr=e[j].to;
            if (!mark[tr]&&findroot(e[j].from)!=findroot(tr))
            {
                ttt--;
                link(e[j].from,tr);
            }
        }
        ans[i]=ttt;
    }
    for (int i=1;i<=q+1;i++) printf("%d\n",ans[i]);
    return 0;
}