题目描述：
输入： 第一行两个整数n和m； 接下来一行中n个整数表示初始点权； 接下来m行每行一个操作如上表所示。
输出： 对于每一个连接操作，若p和q不连通，输出YES，并添加这条边；否则输出NO； 对于每一个删除操作，若p和q间有边，输出YES，并删除这条边，否则输出NO； 对于每一个查询最大及查询和，若p和q连通，输出一行包含一个整数为对应的答案；否则输出一个整数-1。
样例输入： 5 10 1 3 5 4 6 LINK 1 2 LINK 1 3 LINK 2 3 MAX 2 3 UPDATE 1 6 MAX 2 3 LINK 3 5 SUM 3 5 CUT 1 3 SUM 1 5
样例输出： YES YES NO 5 6 YES 11 YES -1
代码如下：
#include <cstdio> #include <algorithm> #define N 50000 using namespace std; inline int Max(int x,int y) { return x>y?x:y; } int n,m,x,y; char s[10]; struct splay{ splay *ch[2],*fa; int val,sum,max_val; bool mark; splay(int x); void maintain(); int dir(); void Reverse(); void push_down(); void push_up(); }*null=new splay(0),*root[N]; splay :: splay(int x) { val=sum=max_val=x; ch[0]=ch[1]=fa=null; mark=false; } void splay :: maintain() { sum=ch[0]->sum+ch[1]->sum+val; max_val=Max(val,Max(ch[0]->max_val,ch[1]->max_val)); } int splay :: dir() { return fa->ch[0]==this?0:(fa->ch[1]==this?1:-1); } void splay :: Reverse() { if(this==null) return ; mark=!mark; swap(ch[0],ch[1]); return ; } void splay :: push_down() { if(this==null) return; if(mark) { ch[0]->Reverse(); ch[1]->Reverse(); mark=false; } return; } void splay :: push_up() { if(~dir()) fa->push_up(); push_down(); } void turn(splay *c,int d) { splay *y=c->ch[d^1]; c->ch[d^1]=y->ch[d]; if(y->ch[d]!=null) y->ch[d]->fa=c; y->ch[d]=c; y->fa=c->fa; int k; if(~(k=c->dir())) c->fa->ch[k]=y; c->fa=y; c->maintain(); y->maintain(); } void splaying(splay *c) { c->push_up(); int d; while(~(d=c->dir())) { if(d==c->fa->dir()) turn(c->fa->fa,d^1); turn(c->fa,d^1); } return; } void Access(splay *c) { splay *tmp=null; while(c!=null) { splaying(c); c->ch[1]=tmp; c->maintain(); tmp=c; c=c->fa; } return; } void Move_to_root(splay *c) { Access(c),splaying(c); c->Reverse(); return; } void Link(splay *x,splay *y) { Move_to_root(x); Access(y),splaying(y); if(x->fa!=null) { printf("NO\n"); return; } printf("YES\n"); x->fa=y; return; } void Cut(splay *x,splay *y) { Move_to_root(x); Access(y),splaying(y); if(y->ch[0]!=x || x->ch[1]!=null) { printf("NO\n"); return; } printf("YES\n"); y->ch[0]=null; y->maintain(); x->fa=null; return; } void query_Max(splay *x,splay *y) { Move_to_root(x); Access(y); splaying(y); if(x->fa==null) printf("-1\n"); else printf("%d\n",y->max_val); return; } void query_Sum(splay *x,splay *y) { Move_to_root(x); Access(y); splaying(y); if(x->fa==null) printf("-1\n"); else printf("%d\n",y->sum); return; } int main() { scanf("%d%d",&n,&m); for(int i=1;i<=n;i++) { scanf("%d",&x); root[i]=new splay(x); } while(m--) { scanf("%s%d%d",s,&x,&y); switch(s[0]) { case 'U': splaying(root[x]); root[x]->val=y; root[x]->maintain(); break; case 'L': Link(root[x],root[y]); break; case 'C': Cut(root[x],root[y]); break; case 'M': query_Max(root[x],root[y]); break; case 'S': query_Sum(root[x],root[y]); break; } } return 0; }