HDU_4010
这个题目由于需要Cut和Join，所以需要用link-cut-tree来写。
无论是Cut还是Join，都涉及到一个基本的操作，就是把一个节点变成根(makeroot)，如果能把makeroot这个操作写成功的话，Cut和Join就比较好完成了。
实际上在进行access(x)的操作之后，如果我们想将x作为根，只需要将这条路径上的边的父子关系都“反向”即可，那么便只要将x旋转到根，然后将这棵splay以及其子树上左右儿子的位置交换，也就是打一个rev(reverse)的标记就可以了。
此外，对于一些细节也需要注意，比如某些操作中x如果和y相等的话是否需要特判一下。
#include<stdio.h> #include<string.h> #define MAXD 300010 #define MAXM 600010 #define INF 0x7fffffff int N, first[MAXD], e, next[MAXM], v[MAXM], q[MAXD]; struct Splay {int pre, ls, rs, key, max, rev, add;bool root;void update(); void pushdown(); void zig(int ); void zag(int ); void splay(int );void renew(){root = true;pre = ls = rs = 0;rev = add = 0;} }sp[MAXD]; int Max(int x, int y) {return x > y ? x : y; } void Splay::update() {max = Max(Max(sp[ls].max, sp[rs].max), key); } void makeadd(int cur, int delta) {if(cur)sp[cur].add += delta, sp[cur].key += delta, sp[cur].max += delta; } void Swap(int &x, int &y) {int t;t = x, x = y, y = t; } void makerev(int cur) {sp[cur].rev ^= 1;Swap(sp[cur].ls, sp[cur].rs); } void Splay::pushdown() {if(add)makeadd(ls, add), makeadd(rs, add), add = 0;if(rev)makerev(ls), makerev(rs), rev = 0; } void Splay::zig(int x) {int y = rs, fa = pre;rs = sp[y].ls, sp[rs].pre = x;sp[y].ls = x, pre = y;sp[y].pre = fa;if(root)root = false, sp[y].root = true;elsesp[fa].rs == x ? sp[fa].rs = y : sp[fa].ls = y;update(); } void Splay::zag(int x) {int y = ls, fa = pre;ls = sp[y].rs, sp[ls].pre = x;sp[y].rs = x, pre = y;sp[y].pre = fa;if(root)root = false, sp[y].root = true;elsesp[fa].rs == x ? sp[fa].rs = y : sp[fa].ls = y;update(); } void Splay::splay(int x) {int y, z;for(pushdown(); !root;){y = pre;if(sp[y].root)sp[y].pushdown(), pushdown(), sp[y].rs == x ? sp[y].zig(y) : sp[y].zag(y);else{z = sp[y].pre;sp[z].pushdown(), sp[y].pushdown(), pushdown();if(sp[z].rs == y){if(sp[y].rs == x)sp[z].zig(z), sp[y].zig(y);elsesp[y].zag(y), sp[z].zig(z);}else{if(sp[y].ls == x)sp[z].zag(z), sp[y].zag(y);elsesp[y].zig(y), sp[z].zag(z);}}}update(); } void access(int x) {int fx;for(fx = x, x = 0; fx != 0; x = fx, fx = sp[x].pre){sp[fx].splay(fx);sp[sp[fx].rs].root = true;sp[fx].rs = x, sp[x].root = false;sp[fx].update();} } void makeroot(int x) {access(x);sp[x].splay(x);makerev(x); } void prepare() {int i, j, x, rear = 0;sp[0].max = -INF;q[rear ++] = 1;sp[1].renew(), sp[1].max = sp[1].key;for(i = 0; i < rear; i ++){x = q[i];for(j = first[x]; j != -1; j = next[j])if(v[j] != sp[x].pre){sp[v[j]].renew(), sp[v[j]].pre = x, sp[v[j]].max = sp[v[j]].key;q[rear ++] = v[j];}} } void add(int x, int y) {v[e] = y;next[e] = first[x], first[x] = e ++; } void init() {int i, x, y;memset(first, -1, sizeof(first));e = 0;for(i = 1; i < N; i ++){scanf("%d%d", &x, &y);add(x, y), add(y, x);}for(i = 1; i <= N; i ++)scanf("%d", &sp[i].key);prepare(); } void Join(int x, int y) {if(x == y){printf("-1\n");return ;}makeroot(x);makeroot(y);if(sp[x].pre == 0)sp[y].pre = x;elseprintf("-1\n"); } void Cut(int x, int y) {makeroot(x);access(y);sp[y].splay(y);if(sp[x].pre == 0)printf("-1\n");else{int t = sp[y].ls;sp[t].root = true, sp[t].pre = 0, sp[y].ls = 0;sp[y].update();} } void Change(int x, int y, int z) {int fy;makeroot(y);makeroot(x);if(sp[y].pre == 0)printf("-1\n");else{access(x);for(fy = y, y = 0; fy != 0; y = fy, fy = sp[y].pre){sp[fy].splay(fy);if(sp[fy].pre == 0){makeadd(sp[fy].rs, z), makeadd(y, z);sp[fy].key += z;}sp[sp[fy].rs].root = true;sp[fy].rs = y, sp[y].root = false;sp[fy].update();}} } void Query(int x, int y) {int fy;if(x == y){sp[x].splay(x);printf("%d\n", sp[x].key);return ;}makeroot(y);makeroot(x);if(sp[y].pre == 0)printf("-1\n");else{access(x);for(fy = y, y = 0; fy != 0; y = fy, fy = sp[y].pre){sp[fy].splay(fy);if(sp[fy].pre == 0)printf("%d\n", Max(Max(sp[sp[fy].rs].max, sp[y].max), sp[fy].key));sp[sp[fy].rs].root = true;sp[fy].rs = y, sp[y].root = false;sp[fy].update();}} } void solve() {int i, x, y, z, m, op;scanf("%d", &m);for(i = 0; i < m; i ++){scanf("%d%d%d", &op, &x, &y);if(op == 1)Join(x, y);else if(op == 2)Cut(x, y);else if(op == 3){scanf("%d", &z);Change(y, z, x);}elseQuery(x, y);} } int main() {while(scanf("%d", &N) == 1){init();solve();printf("\n");}return 0; }