lca和树上差分
关于lca
lca就是最近公共祖先，也就是两个节点的公共祖先距离节点最近，距离根节点最远的
倍增法求lca
倍增主要用到了二进制拆分的思想
首先明确一个定义， k级祖先 ，若节点x的父节点为x的一级祖先，那么父节点的k级祖先也就是x节点的k+1级祖先
而用倍增法求lca要需要x节点和y节点不停向上跳，知道x节点和y节点的父节点为一个时，那么x（或y）节点的1级祖先就是lca
我们需要一个二维数组来存储x节点的2^i级祖先，因为每个数都是能够被二进制的数拼出来的，所以复杂度便是log（n）。定义这二维数组为F数组，而F数组可以在dfs求节点深度的时候递推求出来
还需要一个dep数组来记录一个节点的深度，因为必须当x和y处于同一个深度时才能同时向上跳。向上跳也就是到自己的父节点，dep数组也可通过递推求出来
另外考虑一种情况，当初始时dep(x) != dep(y) ，这时候为了方便就要统一使x的深度比y大，然后让x先跳到深度和y一样的节点
在二进制拆分时，主要是枚举i来求出2^i，另外i要从大到小枚举
code：
#include<bits/stdc++.h>
#define N 500005
#define M 30
using namespace std;
int n,m,s,cnt;
int head[N],dep[N],g[N][M];
struct node{
int to,nxt;
}f[N << 1];
void add(int a,int b){
f[++cnt].to = b;f[cnt].nxt = head[a];head[a] = cnt;
}
void dfs(int now,int fa){
dep[now] = dep[fa]+1;g[now][0] = fa;
int i = 1;
for(int i = 1 ; i < M ; ++i){
g[now][i] = g[g[now][i-1]][i-1];
}
for(int i = head[now] ; i ; i = f[i].nxt){
if(f[i].to!=fa)
dfs(f[i].to,now);
}
}
int lca(int a,int b){
if(dep[a]<dep[b])swap(a,b);
for(int i = M-1 ; i >=0 ; --i ){
if(dep[g[a][i]] >= dep[b]) a = g[a][i];
}
if(a==b)return a;
for(int i = M-1 ; i >=0 ; --i ){
if(g[a][i]!=g[b][i]){
a = g[a][i];b = g[b][i];
}
}
return g[a][0];
}
int main(){
scanf("%d%d%d",&n,&m,&s);
for(int i = 1 ; i <= n-1 ; ++i ){
int x,y; cin >> x >> y;
add(x , y); add(y , x);
}
dfs(s,0);
for(int i = 1 ; i <= m ; ++i){
int fk,thank;
scanf("%d%d",&fk,&thank);
printf("%d\n",lca(fk,thank));
}
}
重链剖分求lca
树链剖分分为重链剖分和长链剖分，而lca的只是重链剖分的一部分。
首先定义轻重儿子，重儿子也就是一个节点的子节点的子树大小最大的一个节点，轻儿子就是除重儿子外的其他节点。
在 dfs 序重标号时，优先遍历每一个节点的重儿子。保证对于每一条重链，其 dfs 序连续。但以上这种操作在求lca是用不到的。真正用到的是重链和轻链。
由于编号连续，重链一次性可以操作一整条链（配合数据结构），轻链则只能一个节点一个节点操作。
树上路径 x → y 被拆分为了若干段重链与轻链的组合，满足可加性的操作可以依此通过数据结构进行维护。
另外，需要使用两次dfs。第一次主要求出节点x的深度，子树大小，重儿子和父亲节点。第二次要求出任意一个节点所在重链的链头。如果没处在一条重链上，链头就是自己。
求lca的操作主要是通过跳链头实现的，跳链头主要就是查找一个节点的链头的父亲节点，因为如果是链头的话便会一直困在这个链中。而lca要通过两个节点不断交替跳链头，然后直到两点在同一条重链上，便得出了他们的最近公共祖先。
每次跳链头都要让深度更大的先跳，最后输出要输出深度更小的。
code :
树上差分
树上差分不过是将差分算法应用到树上了，分为两种，边差分和点差分。
问题：将x -> y 路径上所有点权都加k，询问点权和。与序列上的差分十分甚至九分的相像啊。首先x -> y 的路径可以转化为 x->lcay->lca两条路径
而序列上的差分既可以做前缀和也可以做后缀和，但树上却只能做后缀和。因为从上至下的路径有时不唯一。lca个节点收到了两次影响，所以两条路径又转化为x->lca1和y->lca
所以点差分的操作就有四步
- b[x] += k;
- b[y] += k;
- b[lca] -= k;
- b[fa[lca]] -= k;
边差分只需要将边转化为点就可以了，对于一条边(x,y)，y的x父节点，将边权作为x的点权处理，这时候操作就只剩3步了，因为不会受到影响
- b[x] += k;
- b[y] += k;
- b[lca] -= 2*k;
题：P3258 [JLOI2014]松鼠的新家
P3128 [USACO15DEC]Max Flow P