HDU_4010
这个题目由于需要Cut和Join，所以需要用link-cut-tree来写。
无论是Cut还是Join，都涉及到一个基本的操作，就是把一个节点变成根(makeroot)，如果能把makeroot这个操作写成功的话，Cut和Join就比较好完成了。
实际上在进行access(x)的操作之后，如果我们想将x作为根，只需要将这条路径上的边的父子关系都“反向”即可，那么便只要将x旋转到根，然后将这棵splay以及其子树上左右儿子的位置交换，也就是打一个rev(reverse)的标记就可以了。
此外，对于一些细节也需要注意，比如某些操作中x如果和y相等的话是否需要特判一下。
#include#include #define MAXD 300010#define MAXM 600010#define INF 0x7fffffffint 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; else sp[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; else sp[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); else sp[y].zag(y), sp[z].zig(z); } else { if(sp[y].ls == x) sp[z].zag(z), sp[y].zag(y); else sp[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; else printf("-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); } else Query(x, y); }}int main(){ while(scanf("%d", &N) == 1) { init(); solve(); printf("\n"); } return 0;}