spa cnblogs 注定 ont ++ 方法 scanf tree edge
搬运:看一道caioj1439
题目描述
一开始给你一棵n个点n-1条边的树,每个点有一个权值wi。
三种操作:
op=1 u v :在点u和点v之间建一条边。
op=2 u v:摧毁点u到点v之间的边。
op=3 w u v:将点u和点v之间路径上的点(包括u,v),权值增加w。
op=4 u v:询问点u到点v之间路径上的点(包括u,v),权值最大值。
当操作违法时(询问一中u,v已经相连,二三四中u,v不联通,一二操作u==v)不进行操作并输出-1。
输入
从文件weight.in中读取输入。
第1行为1个正整数n,表示点的个数。
第2~n行为开始树所有的边,每行两个正整数u,v,代表u和v之间有一条边。
第n+1行有n个正整数,表示一开始点的权值。
下一行为一个正整数m代表下来有m个操作。
以下m行,一行表示一个操作。
行首先输入一个正整数op。
当op=1,2,4时,输入两个正整数u,v
当op=3时,输入三个正整数w,u,v
操作如题意
输出
输出到文件weight.out。
对每个4操作,输出点u到点v之间路径上的点(包括u,v),权值最大值。同时对于违法情况输出-1。
该类动态树问题一个突出点就是动态,假如没有1、2操作当然可以方便的运用树链剖分算法水过(详见第8章 树链剖分)。前一章的伸展树只支持改变树的形态,难以对树的结构进行改变,对于建边删边的操作的需要,我们要运用多棵伸展树组成新树,即解决该类动态树问题的普遍方法,Link-Cut-Tree,俗称LCT。
它跟树链剖分类似,只不过树剖用线段树维护重链,而LCT用伸展树(是不是很高大上),在两棵伸展树之间,如果它们属于同一个LCT,那么将有一条虚边,连接着它们,在不影响伸展树的正常操作前提上,保持应有的连系。
大家可以感性的认识….可以假设一开始问题给出的树边都是虚边,我们人为的在上面画重链,每条重链用一棵伸展树维护他(就跟线段树一个道理嘛,目标是减少暴力枚举的时间,只不过伸展树更加快捷灵活),关键的,如果没有连边删边操作,同伸展树一样,整棵树的结构是不变的。
当然啦,题目也可能给出很多棵树,我们可以臆想一下,这些树都属于0节点的子树,只不过他们连的边被“操作删除”了,这样也是合理的。同样道理,当我们在解决动态树问题的过程中,有时也会出现这棵树被分成多份。也就是说,Link-Cut-Tree本质上这个图可以是一个森林。
讲讲操作吧。
最重要的access(x):令x到当前所处的树的根这条路径成为偏爱路径(相当于树剖的重链),然后用splay维护,这是与树剖最大的不同,这样的灵活性也符合动态树。
make_root(x):令x成为当前树的根,但是!!不是在当前重链中伸展树的根,也不是整个图中所有点的根,而是,x当前所处的树的根! 由于 LCT的Link和Cut操作,注定了整个图可能出现多棵树,树与树之间如果不添加边,都是一个独立的动态树。
Link(x,y):让x成为根,然后连一条虚边到y就OK了。
Cut(x,y):先将x设为根(假设现在是点1)假设y是点6,那我们将1~6的路径设为偏爱路径(放在一棵伸展树里)将6旋转到伸展树的根,可以发现,点1肯定在伸展树的最左端,让y断开与左端的连接就行了。
findroot(x):同理,真正在树中的根肯定在树的最左边,所以说找根其实很简单。
PS:所以在make_root后要让整棵伸展树翻转,比如说将6变为根,1,4都在它左边,这样就不科学了。
如果还有不明白的,可以看caioj的书,还有上caioj1439看视频,视频非常好!!出视频的人改变了我的一生,从未见过有如此懂我的人,他太强了,我崇拜他一辈子!!
- #include < cstdio > #include < iostream > #include < cstring > #include < algorithm > #include < cmath > using namespace std;
- struct node {
- int f,
- d,
- c,
- n,
- son[2],
- mx,
- ad;
- bool fz;
- }
- tr[310000];
- void add(int x) {
- tr[x].d += tr[x].ad;
- tr[x].mx += tr[x].ad;
- int lc = tr[x].son[0],
- rc = tr[x].son[1];
- tr[lc].ad += tr[x].ad;
- tr[rc].ad += tr[x].ad;
- tr[x].ad = 0;
- }
- void update(int x) {
- int lc = tr[x].son[0],
- rc = tr[x].son[1];
- tr[x].c = tr[lc].c + tr[rc].c + tr[x].n;
- if (tr[lc].ad != 0) add(lc);
- if (tr[rc].ad != 0) add(rc);
- if (lc == 0) tr[lc].mx = 0;
- if (rc == 0) tr[rc].mx = 0;
- tr[x].mx = max(max(tr[lc].mx, tr[rc].mx), tr[x].d);
- }
- void reverse(int x) {
- tr[x].fz = false;
- swap(tr[x].son[0], tr[x].son[1]);
- int lc = tr[x].son[0],
- rc = tr[x].son[1];
- tr[lc].fz = 1 - tr[lc].fz;
- tr[rc].fz = 1 - tr[rc].fz;
- }
- void rotate(int x, int w) {
- int f = tr[x].f,
- ff = tr[f].f;
- int R,
- r;
- R = f;
- r = tr[x].son[w];
- tr[R].son[1 - w] = r;
- if (r != 0) tr[r].f = R;
- R = ff;
- r = x;
- if (tr[R].son[0] == f) tr[R].son[0] = r;
- else if (tr[R].son[1] == f) tr[R].son[1] = r;
- tr[r].f = R;
- R = x;
- r = f;
- tr[R].son[w] = r;
- tr[r].f = R;
- update(f);
- update(x);
- }
- int tmp[310000];
- void splay(int x, int rt) {
- int s = 0,
- i = x;
- while (tr[i].f != 0 && (tr[tr[i].f].son[0] == i || tr[tr[i].f].son[1] == i)) {
- tmp[++s] = i;
- i = tr[i].f;
- }
- tmp[++s] = i;
- while (s != 0) {
- i = tmp[s];
- s--;
- if (tr[i].fz == true) reverse(i);
- if (tr[i].ad != 0) add(i);
- }
- while (tr[x].f != rt && (tr[tr[x].f].son[0] == x || tr[tr[x].f].son[1] == x)) //还有虚边啊!
- {
- int f = tr[x].f,
- ff = tr[f].f;
- if (ff == rt || (tr[ff].son[0] != f && tr[ff].son[1] != f)) {
- if (x == tr[f].son[0]) rotate(x, 1);
- else rotate(x, 0);
- } else {
- if (tr[f].son[0] == x && tr[ff].son[0] == f) {
- rotate(f, 1);
- rotate(x, 1);
- } else if (tr[f].son[1] == x && tr[ff].son[0] == f) {
- rotate(x, 0);
- rotate(x, 1);
- } else if (tr[f].son[0] == x && tr[ff].son[1] == f) {
- rotate(x, 1);
- rotate(x, 0);
- } else if (tr[f].son[1] == x && tr[ff].son[1] == f) {
- rotate(f, 0);
- rotate(x, 0);
- }
- }
- }
- }
- int n,
- w[310000];
- void make_tree() {
- for (int i = 0; i <= n; i++) {
- tr[i].f = 0;
- tr[i].mx = tr[i].d = w[i];
- tr[i].c = 1;
- tr[i].n = 1;
- tr[i].son[0] = tr[i].son[1] = 0;
- tr[i].fz = false;
- tr[i].ad = 0;
- }
- }
- void access(int x) //访问x
- //还记得树剖的重儿子吗?这是令点x到整棵动态树的根这条路径变成偏爱路径(相当于树剖的重链),这一条路径就是一棵伸展树。
- {
- int y = 0;
- while (x != 0) {
- splay(x, 0);
- tr[x].son[1] = y;
- if (y != 0) tr[y].f = x;
- y = x;
- x = tr[x].f;
- }
- }
- void makeroot(int x) //让x成为当前树的根
- {
- access(x);
- splay(x, 0); //因为是链,splay之后只有左孩子(上面y=0)
- tr[x].fz = 1 - tr[x].fz; //因为要让x成为整棵树的根,所以x的深度要最小(通过翻转实现),为find_root做准备
- }
- void link(int x, int y) { //为什么可以直接用makeroot??因为判断过x和y的find_root 是否相同,不相同表示x和y是不联通的
- makeroot(x);
- tr[x].f = y;
- access(x); //删去access是没有影响的,但从定义上说应该加上
- }
- void cut(int x, int y) {
- makeroot(x);
- access(y);
- splay(y, 0);
- tr[tr[y].son[0]].f = 0;
- tr[y].son[0] = 0;
- update(y);
- }
- int find_root(int x) //访问完x后,x所属的伸展树的最左端的点就是所在树真正的根,因为伸展树实际意义上就是一条链啊!!
- {
- access(x);
- splay(x, 0);
- while (tr[x].son[0] != 0) x = tr[x].son[0];
- return x;
- }
- void increase(int x, int y, int W) //令x,y处于一棵伸展树,y为根,由于是链,直接更新y的ad就行了
- {
- makeroot(x);
- access(y);
- splay(y, 0);
- tr[y].ad += W;
- }
- int findmax(int x, int y) //同理,这也是一样的
- {
- makeroot(x);
- access(y);
- splay(y, 0);
- update(y);
- return tr[y].mx;
- }
- struct edge {
- int x,
- y;
- }
- e[310000];
- int main() {
- freopen("weight.in", "r", stdin);
- freopen("weight.out", "w", stdout);
- int m,
- op,
- x,
- y,
- W;
- while (scanf("%d", &n) != EOF) {
- for (int i = 1; i < n; i++) scanf("%d%d", &e[i].x, &e[i].y);
- for (int i = 1; i <= n; i++) scanf("%d", &w[i]);
- make_tree();
- for (int i = 1; i < n; i++) link(e[i].x, e[i].y);
- scanf("%d", &m);
- for (int i = 1; i <= m; i++) {
- scanf("%d", &op);
- if (op == 1) {
- scanf("%d%d", &x, &y);
- if (find_root(x) == find_root(y) || x == y) printf("-1\n");
- else link(x, y);
- } else if (op == 2) {
- scanf("%d%d", &x, &y);
- if (find_root(x) != find_root(y) || x == y) printf("-1\n");
- else cut(x, y);
- } else if (op == 3) {
- scanf("%d%d%d", &W, &x, &y);
- if (find_root(x) != find_root(y)) printf("-1\n");
- else increase(x, y, W);
- } else {
- scanf("%d%d", &x, &y);
- if (find_root(x) != find_root(y)) printf("-1\n");
- else printf("%d\n", findmax(x, y));
- }
- }
- printf("\n");
- }
- return 0;
- }
关于树论【动态树问题(LCT)】
来源: http://www.bubuko.com/infodetail-2318885.html