P4847 银河英雄传说V2 题解（Splay）

题目链接

P4847 银河英雄传说V2

解题思路

我天哪！！！\(splay\)在\(rotate\)的时候先\(upd(y)\)再\(upd(x)\)！！以后不能再因为这个\(WA\)一晚上了！！！

AC代码

#include<stdio.h>
#define ls t[x].s[0]
#define rs t[x].s[1]
#define rt t[0].s[1]
struct Splay{
    int f,s[2];
    long long sum,data;
}t[200010];
int tot,siz;
int id(int x){return x==t[t[x].f].s[1];}
int find(int x){while(t[x].f)x=t[x].f;return x;}
void upd(int x){t[x].sum=t[ls].sum+t[rs].sum+t[x].data;}
void connect(int x,int f,int son){if(!x&&!f)return;t[x].f=f;t[f].s[son]=x;}
void rotate(int x){
    int y=t[x].f,r=t[y].f,idx=id(x),idy=id(y),b=t[x].s[idx^1];
    connect(b,y,idx);connect(y,x,idx^1);connect(x,r,idy);
    upd(y);upd(x);
}
void splay(int now,int to){
    while(to!=t[now].f){
        int up=t[now].f;
        if(t[up].f==to)rotate(now);
        else if(id(now)==id(up))rotate(up),rotate(now);
        else rotate(now),rotate(now);
    }
}
long long query(int x,int y){
    if(x==y)return t[x].data;
    if(find(x)!=find(y))return -1;
    splay(x,0);splay(y,x);
    return t[x].data+t[y].data+t[t[y].s[id(y)^1]].sum;
}
int main(){
    int i,n,o,v,m;char a[5]={0};
    scanf("%d%d",&n,&m);
    for(i=1;i<=n;i++)
        scanf("%lld",&t[i].data);
    for(i=0;i<m;i++){
        scanf("%s%d",a,&o);
        if(a[0]=='M'){
            scanf("%d",&v);o=find(o);v=find(v);
            int x=v;
            if(o!=v){
                while(rs)x=rs;
                rs=o;
                t[o].f=x;
                splay(x,0);
            }
        }else if(a[0]=='Q'){
            scanf("%d",&v);
            printf("%lld\n",query(o,v));
        }else{
            splay(o,0);
            t[t[o].s[0]].f=0;
            t[o].s[0]=0;
            upd(o);
        }
    }
    return 0;
}