题目：
http://acm.hdu.edu.cn/showproblem.php?pid=5002
题意：
给一棵树树，提供四种操作
1：删除(x,y)边，添加(a,b)边，保证操作前后都是合法的树
2：修改a--b路径上所有点的权值为x
3：a--b路径上所有点的权值增加d
4：输出a--b路径上的第二大值及出现的次数，这里的第二大指的为严格第二大，即1 1 2 2 3 3 3 的第二大值为2
思路：
算是LCT的模板题，利用LCT的各种操作实现以上功能，这里讲一下怎么删除(x,y)边，因为LCT的基础cut操作只能删除x与x的父结点的连边
changeRoot(x);//调整x为树的根节点
cut(y);//因为x--y边一定存在，x为根，则y的父结点定为x
代码：
#include <iostream>
#include <string.h>
#include <stdio.h>
#include <algorithm>
using namespace std;const int MAXSIZE = 100010;
const int INF = 0x1FFFFFFF;struct Node{int sz;Node *ch[2], *pnt;bool rt;bool rev;bool ischange;int add;int wei;int fir, firnum, sec, secnum;
};Node nodes[MAXSIZE];
Node *null = &nodes[0];
int ncnt;int sortarr[6][2];
void push_up(Node *x){x->sz = 1 + x->ch[0]->sz + x->ch[1]->sz;if (x->ischange){x->fir = x->wei;x->firnum = x->sz;x->sec = 0;}else{sortarr[0][0] = x->wei, sortarr[0][1] = 1;if (x->ch[0] != null)if (x->ch[0]->ischange)sortarr[1][0] = x->ch[0]->wei + x->ch[0]->add, sortarr[1][1] = x->ch[0]->sz, sortarr[2][1] = 0;elsesortarr[1][0] = x->ch[0]->fir + x->ch[0]->add, sortarr[1][1] = x->ch[0]->firnum,sortarr[2][0] = x->ch[0]->sec + x->ch[0]->add, sortarr[2][1] = x->ch[0]->secnum;else sortarr[1][1] = sortarr[2][1] = 0;if (x->ch[1] != null)if (x->ch[1]->ischange)sortarr[3][0] = x->ch[1]->wei + x->ch[1]->add, sortarr[3][1] = x->ch[1]->sz, sortarr[4][1] = 0;elsesortarr[3][0] = x->ch[1]->fir + x->ch[1]->add, sortarr[3][1] = x->ch[1]->firnum,sortarr[4][0] = x->ch[1]->sec + x->ch[1]->add, sortarr[4][1] = x->ch[1]->secnum;else sortarr[3][1] = sortarr[4][1] = 0;int maximum=0;for (int i=1;i<5;++i)if (sortarr[i][1]!=0 && sortarr[i][0] > sortarr[maximum][0])maximum = i;x->fir = sortarr[maximum][0];x->firnum = 0;for (int i=0;i<5;++i)if (sortarr[i][0] == sortarr[maximum][0])x->firnum += sortarr[i][1], sortarr[i][1] = 0;maximum = 0;for (int i=1;i<5;++i)if (sortarr[maximum][1] == 0 || (sortarr[i][1]!=0 && sortarr[i][0] > sortarr[maximum][0]))maximum = i;if (sortarr[maximum][1] != 0){x->sec = sortarr[maximum][0];x->secnum = 0;for (int i=0;i<5;++i)if (sortarr[i][0] == sortarr[maximum][0])x->secnum += sortarr[i][1];}else x->secnum = 0;}
}void update_change(Node *x, int wei){x->add = 0;x->wei = wei;x->ischange = true;x->fir = wei;x->firnum = x->sz;x->secnum = 0;
}void push_down(Node *x){if (x->ischange){if (x->ch[0] != null) update_change(x->ch[0], x->wei);if (x->ch[1] != null) update_change(x->ch[1], x->wei);x->ischange = false;}if (x->add != 0){if (x->ch[0] != null) x->ch[0]->add += x->add;if (x->ch[1] != null) x->ch[1]->add += x->add;x->wei += x->add;x->add = 0;}if (x->rev){swap(x->ch[0],x->ch[1]);x->ch[0]->rev = !x->ch[0]->rev;x->ch[1]->rev = !x->ch[1]->rev;x->rev = false;}
}void debug(){for (int j=1;j<=7;++j){Node *t = nodes+j;cout<<endl<<j<<endl;cout<<"wei: "<<t->wei<<" "<<"add: "<<t->add<<" "<<"ischange: "<<t->ischange<<" "<<"fir: "<<t->fir<<" "<<"firnum: "<<t->firnum<<" "<<"sec: "<<t->sec<<" "<<"secnum: "<<t->secnum<<" "<<endl<<"parent: "<<t->pnt - null<<" "<<"leftchild: "<<t->ch[0] - null<<" "<<"rightchild: "<<t->ch[1] - null <<" "<<"isrev: "<<t->rev<<" "<<"isroot: "<<t->rt<<endl;}cout<<"---------------------------"<<endl;
}Node* newNode(int wei){Node* t = &nodes[ncnt++];t->sz = 1;t->pnt = t->ch[0] = t->ch[1] = null;t->rt = true;t->wei = wei;t->add = 0;t->ischange = false;t->fir = wei;t->firnum = 1;t->sec = -INF;t->secnum = 0;t->rev = false;return t;
}void init(){ncnt = 1;null->sz = 0;null->pnt = null->ch[0] = null->ch[1] = null;
}void srotate(Node *x, bool d){Node *y = x->pnt;y->ch[!d] = x->ch[d];if (x->ch[d] != null)x->ch[d]->pnt = y;x->pnt = y->pnt;if (!y->rt){if (y == y->pnt->ch[d])y->pnt->ch[d] = x;elsey->pnt->ch[!d] = x;}x->ch[d] = y;y->pnt = x;if (y->rt){y->rt = false;x->rt = true;}push_up(y);
}void pushdownAll(Node *x){if (!x->rt) pushdownAll(x->pnt);push_down(x);
}void splay(Node *x){Node *y;pushdownAll(x);while (!x->rt){y = x->pnt;if (x == y->ch[0]){if (!y->rt && y == y->pnt->ch[0]){srotate(y, true);//push_up(y);}srotate(x, true);}else{if (!y->rt && y == y->pnt->ch[1]){srotate(y, false);//push_up(y);}srotate(x, false);}}push_up(x);
}void access(Node* u){Node *v = null;while (u != null){splay(u);u->ch[1]->rt = true;(u->ch[1] = v)->rt = false;push_up(u);v = u;u = u->pnt;}
}void cut(Node* v) {access(v);splay(v);v->ch[0]->rt = true;v->ch[0]->pnt = null;v->ch[0] = null;push_up(v);
}void changeRoot(Node *x){access(x);splay(x);x->rev = !x->rev;
}void link(Node *v, Node *u){changeRoot(v);v->pnt = u;
}int arr[MAXSIZE];int main(){int total;int n,m;int i,j,k;int a,b,c,d;scanf("%d",&total);for (i=1;i<=total;++i){init();printf("Case #%d:\n",i);scanf("%d %d",&n,&m);for (j=1;j<=n;++j){scanf("%d",arr+j);newNode(arr[j]);}for (j=1;j<n;++j){scanf("%d %d",&a,&b);link(nodes+a, nodes+b);}Node *x,*y;for (j=0;j<m;++j){scanf("%d",&a);//debug();switch (a){case 1:scanf("%d %d %d %d",&a,&b,&c,&d);x = nodes+a; y = nodes+b;changeRoot(x);cut(y);//debug();link(nodes+c, nodes+d);break;case 2:scanf("%d %d %d",&a,&b,&c);x = nodes + a; y = nodes + b;changeRoot(x);access(y);splay(x);x -> ischange = true;x -> wei = c;x -> add = 0;break;case 3:scanf("%d %d %d",&a,&b,&c);x = nodes + a, y = nodes + b;changeRoot(x);access(y);splay(x);x -> add += c;break;case 4:scanf("%d %d",&a,&b);x = nodes + a, y = nodes + b;changeRoot(x);//debug();access(y);splay(x);if (x->secnum == 0) printf("ALL SAME\n");else printf("%d %d\n", x->sec, x->secnum);break;}//debug();}}return 0;
}
