动态树LCT 模板

本文主要是介绍动态树LCT 模板，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目描述：

输入：
第一行两个整数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;
}

这篇关于动态树LCT 模板的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---