传送门

直接暴力用splay维护轻重链就行了,显然改变次数是均摊log的。对LCT的那套势能分析应该也一样适用(不过没仔细研究),所以应该是一个log的(就算不适用也是两个log)。

#include <bits/stdc++.h>
#define MAXN 200010
#define LL long long

struct node{
    int ch[2],p,lp;
    int tag,v,minv;
}a[MAXN];

int n,m;
int ch[MAXN][2],sc[MAXN],cc[MAXN],pre[MAXN],d[MAXN];
int size[MAXN];
LL ans;

void pushdown(int x){
    if(a[x].ch[0]) a[a[x].ch[0]].tag+=a[x].tag,a[a[x].ch[0]].v+=a[x].tag,a[a[x].ch[0]].minv+=a[x].tag;
    if(a[x].ch[1]) a[a[x].ch[1]].tag+=a[x].tag,a[a[x].ch[1]].v+=a[x].tag,a[a[x].ch[1]].minv+=a[x].tag;
    a[x].tag=0;
}

void pushup(int x){
    a[x].minv=a[x].v;
    if(a[x].ch[0] && a[a[x].ch[0]].minv<a[x].minv) a[x].minv=a[a[x].ch[0]].minv;
    if(a[x].ch[1] && a[a[x].ch[1]].minv<a[x].minv) a[x].minv=a[a[x].ch[1]].minv;
}

void rotate(int x){
    int p=a[x].p;
    int d=a[p].ch[0]==x;
    if(a[p].p) a[a[p].p].ch[a[a[p].p].ch[1]==p]=x;
    else{
        a[x].lp=a[p].lp;
        a[p].lp=0;
    }
    a[x].p=a[p].p;
    a[p].ch[d^1]=a[x].ch[d];
    if(a[x].ch[d]) a[a[x].ch[d]].p=p;
    a[x].ch[d]=p;
    a[p].p=x;
    pushup(p);
}

void clearTag(int x){
    static int ls[MAXN];
    int len=0;
    while(x) ls[++len]=x,x=a[x].p;
    while(len) pushdown(ls[len--]);
}

void splay(int x){
    clearTag(x);
    while(a[x].p){
        int p=a[x].p;
        if(!a[p].p) rotate(x);
        else{
            int q=a[p].p;
            if((a[q].ch[1]==p)==(a[p].ch[1]==x)) rotate(p),rotate(x);
            else rotate(x),rotate(x);
        }
    }
    pushup(x);
}

int find(int x){
    pushdown(x);
    if(a[x].ch[1] && a[a[x].ch[1]].minv<0) return find(a[x].ch[1]);
    if(a[x].v<0) return x;
    return find(a[x].ch[0]);
}

void access(int x){
    if(x==1) return;
    if(!(--d[pre[x]])) ans-=cc[pre[x]];
    splay(x);
    if(a[x].ch[0]){
        a[a[x].ch[0]].p=0;
        a[a[x].ch[0]].lp=a[x].lp;
        x=a[x].ch[0];
        a[x].tag--; a[x].v--; a[x].minv--;
        pushdown(x);
        pushup(x);
    }else{
        int t=a[x].lp;
        a[x].lp=0;
        x=t;
        splay(x);
        if(a[x].ch[0]) a[a[x].ch[0]].tag--,a[a[x].ch[0]].v--,a[a[x].ch[0]].minv--;
        a[x].v++;
        pushup(x);
    }
    while(1){
        if(a[x].minv>=0){
            x=a[x].lp;
            if(!x) break;
            splay(x);
            if(a[x].ch[0]) a[a[x].ch[0]].tag--,a[a[x].ch[0]].v--,a[a[x].ch[0]].minv--;
            a[x].v++;
            pushup(x);
            continue;
        }
        x=find(x);
        splay(x);
        ans-=cc[x];
        cc[x]^=sc[x];
        if(d[x]==0) cc[x]=0;
        ans+=cc[x];
        if(a[x].ch[1]){
            a[a[x].ch[1]].lp=x;
            a[a[x].ch[1]].p=0;
        }
        splay(cc[x]);
        a[x].ch[1]=cc[x];
        if(a[x].ch[1]){
            a[a[x].ch[1]].lp=0;
            a[a[x].ch[1]].p=x;
        }
        a[x].v=-a[x].v;
        pushup(x);
    }
}

void dfs(int x){
    size[x]=1;
    if(ch[x][0]) dfs(ch[x][0]),size[x]+=size[ch[x][0]];
    if(ch[x][1]) dfs(ch[x][1]),size[x]+=size[ch[x][1]];
    if(size[x]>1){
        if(size[ch[x][0]]>=size[ch[x][1]]) cc[x]=ch[x][0];
        else cc[x]=ch[x][1];
        ans+=cc[x];
        a[x].v=size[cc[x]]-size[sc[x]^cc[x]];
        a[x].ch[1]=cc[x];
        a[cc[x]].p=x;
        pre[cc[x]]=x;
        d[x]++;
        if(sc[x]^cc[x]) a[sc[x]^cc[x]].lp=x,pre[sc[x]^cc[x]]=x,d[x]++;
        pushup(x);
    }
}

int main(){
#ifdef DEBUG
    freopen("132.in","r",stdin);
#endif
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%d%d",&ch[i][0],&ch[i][1]);
        sc[i]=ch[i][0]^ch[i][1];
    }
    dfs(1);
    printf("%lld\n",ans);
    scanf("%d",&m);
    while(m--){
        int x;
        scanf("%d",&x);
        access(x);
        printf("%lld\n",ans);
    }
}