树链剖分
“在一棵树上进行路径的修改、求极值、求和”乍一看只要线段树就能轻松解决，实际上，仅凭线段树是不能搞定它的。我们需要用到一种貌似高级的复杂算法——树链剖分。
树链，就是树上的路径。剖分，就是把路径分类为重链和轻链。
记siz[v]表示以v为根的子树的节点数，dep[v]表示v的深度(根深度为1)，top[v]表示v所在的链的顶端节点，fa[v]表示v的父亲，son[v]表示与v在同一重链上的v的儿子节点（姑且称为重儿子），w[v]表示v与其父亲节点的连边（姑且称为v的父边）在线段树中的位置。只要把这些东西求出来，就能用logn的时间完成原问题中的操作。
重儿子：siz[u]为v的子节点中siz值最大的，那么u就是v的重儿子。
轻儿子：v的其它子节点。
重边：点v与其重儿子的连边。
轻边：点v与其轻儿子的连边。
重链：由重边连成的路径。
轻链：轻边。
剖分后的树有如下性质：
性质1：如果(v,u)为轻边，则siz[u] 2 < siz[v]；
*性质2：从根到某一点的路径上轻链、重链的个数都不大于logn。
算法实现：
我们可以用两个dfs来求出fa、dep、siz、son、top、w。
dfs_1：把fa、dep、siz、son求出来，比较简单，略过。
dfs_2：⒈对于v，当son[v]存在（即v不是叶子节点）时，显然有top[son[v]] = top[v]。线段树中，v的重边应当在v的父边的后面，记w[son[v]] = totw+1，totw表示最后加入的一条边在线段树中的位置。此时，为了使一条重链各边在线段树中连续分布，应当进行dfs_2(son[v])；
⒉对于v的各个轻儿子u，显然有top[u]=u，并且w[u]=totw+1，进行dfs_2过程。这就求出了top和w。将树中各边的权值在线段树中更新，建链和建线段树的过程就完成了。
修改操作：例如将u到v的路径上每条边的权值都加上某值x。
一般人需要先求LCA，然后慢慢修改u、v到公共祖先的边。
记f1 = top[u]，f2 = top[v]。
当f1 <> f2时：不妨设dep[f1] >= dep[f2]，那么就更新u到f1的父边的权值(logn)，并使u = fa[f1]。
当f1 = f2时：u与v在同一条重链上，若u与v不是同一点，就更新u到v路径上的边的权值(logn)，否则修改完成；
重复上述过程，直到修改完成。
求和、求极值操作：类似修改操作，但是不更新边权，而是对其求和、求极值。
如图所示，较粗的为重边，较细的为轻边。节点编号旁边有个红色点的表明该节点是其所在链的顶端节点。边旁的蓝色数字表示该边在线段树中的位置。图中1-4-9-13-14为一条重链。
当要修改11到10的路径时。
第一次迭代：u = 11，v = 10，f1 = 2，f2 = 10。此时dep[f1] < dep[f2]，因此修改线段树中的5号点，v = 4, f2 = 1；
第二次迭代：dep[f1] > dep[f2]，修改线段树中10--11号点。u = 2，f1 = 2；
第三次迭代：dep[f1] > dep[f2]，修改线段树中9号点。u = 1，f1 = 1；
第四次迭代：f1 = f2且u = v，修改结束。
题意：给一棵树，并给定各个点权的值，然后有3种操作：
I C1 C2 K: 把C1与C2的路径上的所有点权值加上K
D C1 C2 K：把C1与C2的路径上的所有点权值减去K
Q C：查询节点编号为C的权值
分析：典型的树链剖分题目，先进行剖分，然后用线段树去维护即可
#include<cstdio>
#include<cstring>
#include<stack>
#include<algorithm>
using namespace std;
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
typedef int lld;
stack<int> ss;
const int maxn = 200010;
const int inf = ~0u>>2;
int M[maxn<<2];
int add[maxn<<2];
struct node{
int s,t,w,next;
}edge[maxn*2];
int E,n;
int size[maxn] , fa[maxn] , heavy[maxn] , head[maxn] , vis[maxn];
int dep[maxn] , rev[maxn] , num[maxn] , cost[maxn] ,w[maxn];
int Seg_size;
inline void Max(int &x,int y){if(x<y) x=y;}
int find(int x){return x==fa[x]?x:fa[x]=find(fa[x]);}
void add_edge(int s,int t,int w)
{
edge[E].w=w;
edge[E].s=s;
edge[E].t=t;
edge[E].next=head[s];
head[s]=E++;
}
void dfs(int u,int f)
{
int mx=-1,e=-1;
size[u]=1;
for(int i=head[u];i!=-1;i=edge[i].next)
{
int v=edge[i].t;
if(v==f) continue;
edge[i].w=edge[i^1].w=w[v];
dep[v]=dep[u]+1;
rev[v]=i^1;
dfs(v,u);
size[u]+=size[v];
if(size[v]>mx)
{
mx=size[v];
e=i;
}
}
heavy[u]=e;
if(e!=-1) fa[edge[e].t]=u;
}
inline void pushup(int rt){
M[rt]=M[rt<<1]+M[rt<<1|1];
}
void pushdown(int rt,int m){
if(add[rt]){
add[rt<<1]+=add[rt];
add[rt<<1|1]+=add[rt];
M[rt<<1]+=add[rt]*(m-(m>>1));
M[rt<<1|1]+=add[rt]*(m>>1);
add[rt]=0;
}
}
void build(int l,int r,int rt){
M[rt]=add[rt]=0;
if(l==r){
return ;
}
int m=(l+r)>>1;
build(lson);
build(rson);
}
void update(int L,int R,int val,int l,int r,int rt){
if(L<=l&&r<=R){
M[rt]+=val;
add[rt]+=val;
return ;
}
pushdown(rt,r-l+1);
int m=(l+r)>>1;
if(L<=m) update(L,R,val,lson);
if(R>m) update(L,R,val,rson);
pushup(rt);
}
lld query(int L,int R,int l,int r,int rt){
if(L<=l&&r<=R){
return M[rt];
}
pushdown(rt,r-l+1);
int m=(l+r)>>1;
lld ret=0;
if(L<=m) ret+=query(L,R,lson);
if(R>m) ret+=query(L,R,rson);
return ret;
}
void prepare()
{
int i;
build(1,n,1);
memset(num,-1,sizeof(num));
dep[0]=0;Seg_size=0;
for(i=0;i<n;i++) fa[i]=i;
dfs(0,0);
for(i=0;i<n;i++)
{
if(heavy[i]==-1)
{
int pos=i;
while(pos && edge[heavy[edge[rev[pos]].t]].t == pos)
{
int t=rev[pos];
num[t]=num[t^1]=++Seg_size;//printf("pos=%d val=%d t=%d\n",Seg_size,edge[t].w,t);
update(Seg_size,Seg_size,edge[t].w,1,n,1);
pos=edge[t].t;
}
}
}
}
int lca(int u,int v)
{
while(1)
{
int a=find(u),b=find(v);
if(a==b) return dep[u] < dep[v] ? u : v;//a,b在同一条重链上
else if(dep[a]>=dep[b]) u=edge[rev[a]].t;
else v=edge[rev[b]].t;
}
}
void CH(int u,int lca,int val)
{
while(u!=lca)
{
int r=rev[u];//printf("r=%d\n",r);
if(num[r]==-1) edge[r].w+=val,u=edge[r].t;
else
{
int p=fa[u];
if(dep[p] < dep[lca]) p=lca;
int l=num[r];
r=num[heavy[p]];
update(l,r,val,1,n,1);
u=p;
}
}
}
void change(int u,int v,int val)
{
int p=lca(u,v);// printf("p=%d\n",p);
CH(u,p,val);
CH(v,p,val);
if(p){
int r=rev[p];
if(num[r]==-1) {
edge[r^1].w+=val;//在此处发现了我代码的重大bug
edge[r].w+=val;
}
else update(num[r],num[r],val,1,n,1);
}//根节点，特判
else w[p]+=val;
}
lld solve(int u)
{
if(!u) return w[u];//根节点，特判
else
{
int r=rev[u];
if(num[r]==-1) return edge[r].w;
else return query(num[r],num[r],1,n,1);
}
}
int main()
{
int t,i,a,b,c,m,ca=1,p;
while(scanf("%d%d%d",&n,&m,&p)!=EOF)
{
memset(head,-1,sizeof(head));
E=0;
for(i=0;i<n;i++) scanf("%d",&w[i]);
for(i=0;i<m;i++)
{
scanf("%d%d",&a,&b);a--;b--;
add_edge(a,b,0);
add_edge(b,a,0);
}
prepare();
char op[10];
while(p--)
{
scanf("%s",&op);
if(op[0]=='I')
{
scanf("%d%d%d",&a,&b,&c);a--;b--;
change(a,b,c);
}
else if(op[0]=='D')
{
scanf("%d%d%d",&a,&b,&c);a--;b--;
change(a,b,-c);
}
else
{
scanf("%d",&a);a--;
printf("%d\n",solve(a));
}
}
}
return 0;
}
Link-Cut Tree
动态树(Link-Cut Tree)是一类要求维护森林的连通性的题的总称，这类问题要求维护某个点到根的某些数据，支持树的切分，合并，以及对子树的某些操作。其中解决这一问题的某些简化版（不包括对子树的操作）的基础数据结构就是LCT(link-cut tree)。
LCT的大体思想类似于树链剖分中的轻重链剖分,轻重链剖分是处理出重链来，由于重链的定义和树链剖分是处理静态树所限，重链不会变化，变化的只是重链上的边或点的权值，由于这个性质，我们用线段树来维护树链剖分中的重链，但是LCT解决的是动态树问题（包含静态树），所以需要用更灵活的splay来维护这里的“重链”。
定义：
首先来定义一些量：
access(X)：表示访问X点（之后会有说明）。
Preferred child（偏爱子节点）：如果最后被访问的点在X的儿子P节点的子树中，那么称P为X的Preferred child，如果一个点被访问，他的Preferred child为null(即没有)。
Preferred edge（偏爱边）：每个点到自己的Preferred child的边被称为Preferred edge。
Preferred path（偏爱路径）：由Preferred edge组成的不可延伸的路径称为Preferred path。
这样我们可以发现一些比较显然的性质，每个点在且仅在一条Preferred path上，也就是所有的Preferred path包含了这棵树上的所有的点，这样一颗树就可以由一些Preferred path来表示（类似于轻重链剖分中的重链），我们用splay来维护每个条Preferred path，关键字为深度，也就是每棵splay中的点左子树的深度都比当前点小，右节点的深度都比当前节点的深度大。这样的每棵splay我们称为Auxiliary tree(辅助树)，每个Auxiliary tree的根节点保存这个Auxiliary tree与上一棵Auxiliary tree中的哪个点相连。这个点称作他的Path parent。
操作：
access(X)：首先由于preferred path的定义，如果一个点被访问，那么这个点到根节点的所有的边都会变成preferred edge，由于每个点只有一个preferred child，所以这个点到根节点路径上的所有的点都会和原来的preferred child断开，连接到这条新的preferred path上。假设访问X点，那么先将X点旋转到对应Auxiliary tree的根节点，然后因为被访问的点是没有preferred child的，所以将Auxiliary tree中根节点(X)与右子树的边断掉，左节点保留，将这个树的path parent旋转到对应Auxiliary tree的根节点，断掉右子树，连接这个点与X点，相当于合并两棵Auxiliary tree，不断地重复这一操作，直到当前X所在Auxiliary tree的path parent为null时停止，表示已经完成当前操作。
find root(x)：找到某一点所在树的根节点（维护森林时使用）。只需要access(X)，然后将X节点旋到对应Auxiliary tree的根节点，然后找到这个Auxiliary tree中最左面的点。
cut(x)：断掉X节点和其父节点相连的边。首先access(X)，然后将X旋转到对应Auxiliary tree的根节点，然后断掉Auxiliary tree中X和左节点相连的边。
link(join)(x,y)：连接点x到y点上。即让x称为y的子节点。因为x为y的子节点后，在原x的子树中，x点到根节点的所有的点的深度会被翻转过来，所以先access(x)，然后在对应的Auxiliary tree中将x旋转到根节点，，然后将左子树翻转(splay中的reverse操作)，然后access(y)，将y旋转到对应Auxiliary tree中的根节点，将x连到y就行了。
LCT的模板题，只需Link和Cut操作
#include<cstdio>
#include<cstring>
#include<iostream>
#define MAXN 50010
using namespace std;
int n;
struct LCT {
int bef[MAXN], pre[MAXN], next[MAXN][2];
void Init() {
memset(pre, 0, sizeof(pre));
memset(next, 0, sizeof(next));
}
inline void Rotate(int x, int kind) {
int y, z;
y = pre[x];
z = pre[y];
next[y][!kind] = next[x][kind];
pre[next[x][kind]] = y;
next[z][next[z][1] == y] = x;
pre[x] = z;
next[x][kind] = y;
pre[y] = x;
}
void Splay(int x) {
int rt;
for (rt = x; pre[rt]; rt = pre[rt])
;
if (x != rt) {
bef[x] = bef[rt];
bef[rt] = 0;
while (pre[x]) {
if (next[pre[x]][0] == x)
Rotate(x, 1);
else
Rotate(x, 0);
}
}
}
void Access(int x) {
int father;
for (father = 0; x; x = bef[x]) {
Splay(x);
pre[next[x][1]] = 0;
bef[next[x][1]] = x;
next[x][1] = father;
pre[father] = x;
bef[father] = 0;
father = x;
}
}
int Query(int x) {
Access(x);
Splay(x);
while (next[x][0])
x = next[x][0];
return x;
}
void Cut(int x) {
Access(x);
Splay(x);
bef[next[x][0]] = bef[x];
bef[x] = 0;
pre[next[x][0]] = 0;
next[x][0] = 0;
}
void Join(int x, int y) {
if (y == 0)
Cut(x);
else {
int tmp;
Access(y);
Splay(y);
for (tmp = x; pre[tmp]; tmp = pre[tmp])
;
if (tmp != y) {
Cut(x);
bef[x] = y;
}
}
}
} lct;
int INT() {
char ch;
int res;
while (ch = getchar(), !isdigit(ch))
;
for (res = ch - '0'; ch = getchar(), isdigit(ch);)
res = res * 10 + ch - '0';
return res;
}
char CHAR() {
char ch, res;
while (res = getchar(), !isalpha(res))
;
while (ch = getchar(), isalpha(ch))
;
return res;
}
int main() {
bool flag = true;
char ch;
int i, x, y, q;
while (~scanf("%d", &n)) {
if (flag)
flag = false;
else
putchar('\n');
lct.Init();
for (i = 1; i <= n; i++)
lct.bef[i] = INT();
q = INT();
while (q--) {
ch = CHAR();
if (ch == 'Q') {
x = INT();
printf("%d\n", lct.Query(x));
} else {
x = INT(), y = INT();
lct.Join(x, y);
}
}
}
return 0;
}
题目大意：指定一颗树上有3个操作：询问操作,询问a点和b点之间的路径上最长的那条边的长度；取反操作，将a点和b点之间的路径权值都取相反数；变化操作，把某条边的权值变成指定的值。
#include<cstdio>
#include<cstring>
#include<queue>
#include<iostream>
#include<algorithm>
#define MAXN 100010
#define MAXM 200010
#define oo 0x7FFFFFFF
using namespace std;
bool vis[MAXN];
int first[MAXN], next[MAXM], v[MAXM], cost[MAXM], e;
struct LCT {
bool neg[MAXN];
int maxi[MAXN], mini[MAXN];
int bef[MAXN], belong[MAXN];
int next[MAXN][2], pre[MAXN], key[MAXN];
void Init() {
memset(next, 0, sizeof(next));
memset(pre, 0, sizeof(pre));
memset(neg, false, sizeof(neg));
maxi[0] = -oo;
mini[0] = oo;
}
inline void PushUp(int x) {
maxi[x] = key[x];
if (next[x][0])
maxi[x] = max(maxi[x], maxi[next[x][0]]);
if (next[x][1])
maxi[x] = max(maxi[x], maxi[next[x][1]]);
mini[x] = key[x];
if (next[x][0])
mini[x] = min(mini[x], mini[next[x][0]]);
if (next[x][1])
mini[x] = min(mini[x], mini[next[x][1]]);
}
inline void Not(int x) {
if (x) {
neg[x] ^= true;
swap(maxi[x], mini[x]);
key[x] = -key[x];
maxi[x] = -maxi[x];
mini[x] = -mini[x];
}
}
inline void PushDown(int x) {
if (neg[x]) {
Not(next[x][0]);
Not(next[x][1]);
neg[x] = false;
}
}
void Rotate(int x, int kind) {
int y, z;
y = pre[x];
z = pre[y];
PushDown(y);
PushDown(x);
next[y][!kind] = next[x][kind];
pre[next[x][kind]] = y;
next[z][next[z][1] == y] = x;
pre[x] = z;
next[x][kind] = y;
pre[y] = x;
PushUp(y);
}
void Splay(int x) {
int rt;
for (rt = x; pre[rt]; rt = pre[rt])
;
if (rt != x) {
bef[x] = bef[rt];
bef[rt] = 0;
PushDown(x);
while (pre[x]) {
if (next[pre[x]][0] == x)
Rotate(x, 1);
else
Rotate(x, 0);
}
PushUp(x);
}
}
void Access(int x) {
int father;
for (father = 0; x; x = bef[x]) {
Splay(x);
PushDown(x);
pre[next[x][1]] = 0;
bef[next[x][1]] = x;
next[x][1] = father;
pre[father] = x;
bef[father] = 0;
father = x;
PushUp(x);
}
}
void Change(int x, int y) {
int t;
t = belong[x - 1];
Splay(t);
key[t] = y;
}
void Negate(int x, int y) {
Access(y);
for (y = 0; x; x = bef[x]) {
Splay(x);
if (!bef[x]) {
Not(y);
Not(next[x][1]);
return;
}
PushDown(x);
pre[next[x][1]] = 0;
bef[next[x][1]] = x;
next[x][1] = y;
pre[y] = x;
bef[y] = 0;
y = x;
PushUp(x);
}
}
int Query(int x, int y) {
Access(y);
for (y = 0; x; x = bef[x]) {
Splay(x);
if (!bef[x])
return max(maxi[y], maxi[next[x][1]]);
PushDown(x);
pre[next[x][1]] = 0;
bef[next[x][1]] = x;
next[x][1] = y;
pre[y] = x;
bef[y] = 0;
y = x;
PushUp(x);
}
return 0;
}
} lct;
int INT() {
char ch;
int res;
bool neg;
while (ch = getchar(), !isdigit(ch) && ch != '-')
;
if (ch == '-') {
res = 0;
neg = true;
} else {
res = ch - '0';
neg = false;
}
while (ch = getchar(), isdigit(ch))
res = res * 10 + ch - '0';
return neg ? -res : res;
}
char CHAR() {
char ch, res;
while (res = getchar(), !isalpha(res))
;
while (ch = getchar(), isalpha(ch))
;
return res;
}
inline void AddEdge(int x, int y, int val) {
v[e] = y;
cost[e] = val;
next[e] = first[x];
first[x] = e++;
}
void BFS(int x) {
int i, y;
queue<int> q;
memset(vis, false, sizeof(vis));
vis[x] = true;
q.push(x);
while (!q.empty()) {
x = q.front();
q.pop();
for (i = first[x]; i != -1; i = next[i]) {
y = v[i];
if (!vis[y]) {
lct.bef[y] = x;
lct.key[y] = cost[i];
lct.belong[i >> 1] = y;
vis[y] = true;
q.push(y);
}
}
}
}
int main() {
int c, i;
char ch;
int n, x, y, val;
c = INT();
while (c--) {
n = INT();
lct.Init();
memset(first, -1, sizeof(first));
for (e = 0, i = 1; i < n; i++) {
x = INT(), y = INT(), val = INT();
AddEdge(x, y, val);
AddEdge(y, x, val);
}
BFS(1);
while (ch = CHAR(), ch != 'D') {
x = INT(), y = INT();
if (ch == 'Q')
printf("%d\n", lct.Query(x, y));
else if (ch == 'C')
lct.Change(x, y);
else
lct.Negate(x, y);
}
}
return 0;
}