经常听到大佬说树剖云云，大概学一下。

  • 树链剖分

树剖通过将整棵树划分为多条重链，将其转换为线性结构，方便我们使用其他数据结构维护这个树的信息。

概念：

重儿子：对于每一个非叶子节点，它的儿子中子树节点数最大的儿子，为该节点的重儿子
轻儿子：对于每一个非叶子节点，它的儿子中重儿子以外的所有儿子为轻儿子
叶子节点没有重儿子也没有轻儿子（因为它没有儿子。。）
重边：一个父亲连接他的重儿子的边称为重边
轻边：剩下的即为轻边
重链：相邻重边连起来的 连接一条重儿子 的链叫重链 （对于叶子节点，若其为轻儿子，则有一条以自己为起点的长度为1的链，每一条重链以轻儿子为起点）
////偷来的图/////
可以看到重新编号之后的树中，每条链的编号是连续的，每个子树的编号也是连续的，那么对于子树上的操作和查询，就可以通过线段树对区间的维护实现。

DFS大致流程：

dfs1处理：
  • 以每个点为根的子树节点数size
  • 每个点的重儿子son （通过比较节点数可以很方便实现）
  • 每个结点的父亲fa
  • 每个结点的深度deep（对优化很重要）
dfs2处理：
  • 为每个结点重新编号（如果要结合一些数据结构的话）
  • 为新编好的结点赋值（再开一个数组作为数据数组）
  • 获得每个点所在链的结点编号top
（这里注意dfs2的时候对儿子先重后轻处理，这样每个链和每个子树的编号才能连续）

  • 树链剖分与LCA

用树链求LCA思想与倍增很像
对a,b要求其lca，从当前节点中链头深度大的一点开始向上跳，每次跳到当前结点所在链的顶点的父节点
当两点在同一条链时退出循环，返回深度较小的点
代更。
洛谷链接：https://www.luogu.org/problem/P3398 
#include<bits/stdc++.h>
using namespace std;
#define C getchar()
typedef long long ll;
#define pi acos(-1.0)
#define INF 0x3f3f3f3f
#define mod 1000000007
const int MAXN = 1e5 + 10;
#define pii pair<int, int>
#define endll printf("\n")
#define stop system("pause")
#define lson rt << 1, l, mid
#define lowbit(x) ((x) & (-x))
#define rson rt * 2 + 1, mid + 1, r
#define FOR(i,a,b) for(int i=a;i<=b;i++)
#define mem(a, b) memset(a, b, sizeof(a))
inline void rd(int &s)
{
    s = 0;int t = 1, k = C;
    for (; k < '0' || k > '9'; k = C)if (k == '-') t = -1;
    for (; k >= '0' && k <= '9'; k = C) s = (s << 1) + (s << 3) + (k ^ 48);
    s *= t;
}
int  n,q;
vector<int>g[MAXN];
//dfs1
int son[MAXN],fa[MAXN];
int dep[MAXN],size[MAXN];
//dfs2
int top[MAXN];
inline void dfs1(int u,int pre,int deep)
{
    size[u]=1;dep[u]=deep;fa[u]=pre;
    int maxson=-1;
    for(int i=0;i<g[u].size();i++)
    {
        int v=g[u][i];
        if(v==pre) continue;
        dfs1(v,u,deep+1);
        size[u]+=size[v];
        if(size[v]>maxson) maxson=size[v],son[u]=v;
    }
}
inline void dfs2(int x,int topx)//
{
    top[x]=topx;
    if(son[x]==-1) return ;
    dfs2(son[x],topx);
    for(int i=0;i<g[x].size();i++)
    {
        int v=g[x][i];
        if(v==fa[x]||v==son[x]) continue;
        dfs2(v,v);
    }
}
int lca(int x,int y)
{
    for(;top[x]!=top[y];x=fa[top[x]])
        if(dep[top[x]]<dep[top[y]]) swap(x,y);//
    if(dep[x]>dep[y]) swap(x,y);
    return x;
}
int main()
{
    rd(n);rd(q);
    FOR(i,1,n-1)
    {
        int u,v;rd(u);rd(v);
        g[u].push_back(v);
        g[v].push_back(u);
    }
    //
    mem(son,-1);
    dfs1(1,0,1);
    dfs2(1,0);
    //
    while(q--)
    {
        int a,b,c,d;
        rd(a),rd(b),rd(c),rd(d);
        int s=lca(a,b),t=lca(c,d);
        if(dep[s]<dep[t]) 
            swap(s,t),swap(a,c),swap(b,d);
        if(lca(s,c)==s||lca(s,d)==s)
            printf("Y\n");
        else 
            printf("N\n");
    }
    //stop;
    return 0;
}

树链剖分与线段树

今天写动归写不下去。。只好来写树剖
链接：https://www.luogu.org/problem/P4092
利用树链维护子树信息时，一个节点的子树即为id[x]~id[x]+size[x]-1的区间
操作1：把某点值变为1 ，线段树维护值为1的最大编号，初始值为1 。更改某点时，更改该点的子树那部分的区间最大值。 
操作2：查询到x~1路径上值为1的编号最大的原编号 ，利用树剖+线段树在向上跳的时候求出最大值
一开始开小了RE了，，其他就是板子？？？
太好了丰富了我的板子） 
#include<bits/stdc++.h>
using namespace std;
#define C getchar()
typedef long long ll;
#define pi acos(-1.0)
#define INF 0x3f3f3f3f
#define mod 1000000007
const int MAXN = 1e5 + 10;
#define pii pair<int, int>
#define endll printf("\n")
#define stop system("pause")
#define lowbit(x) ((x) & (-x))
#define Temp template<typename T>
#define FOR(i,a,b) for(int i=a;i<=b;i++)
#define mem(a, b) memset(a, b, sizeof(a))
Temp inline void rd(T &s)
{
    s = 0;T t = 1, k = C;
    for (; k < '0' || k > '9'; k = C)if (k == '-') t = -1;
    for (; k >= '0' && k <= '9'; k = C) s = (s << 1) + (s << 3) + (k ^ 48);
    s *= t;
}
int  n;
vector<int>g[MAXN];
//dfs1
int son[MAXN],fa[MAXN];
int dep[MAXN],size[MAXN];
//dfs2
int top[MAXN],id[MAXN],rk[MAXN];
//tree
int cnt;
struct Segment_Tree
{
    #define lson rt<<1,l,mid
    #define rson rt<<1|1,mid+1,r
    int maxv[MAXN<<2];int lazy[MAXN<<2];
    inline int ls(int p) {return p<<1;}
    inline int rs(int p) {return p<<1|1;}
    void push_up(int p) {maxv[p] = max(maxv[ls(p)],maxv[rs(p)]);}
    void push_down(int p)
    {
        maxv[ls(p)]=max(maxv[ls(p)],lazy[p]);
        maxv[rs(p)]=max(maxv[rs(p)],lazy[p]);
        lazy[ls(p)]=max(lazy[ls(p)],lazy[p]);
        lazy[rs(p)]=max(lazy[rs(p)],lazy[p]);
        lazy[p]=0;
    }
    void build(int rt,int l,int r)
    {
        lazy[rt]=0;
        if(l==r) {maxv[rt]=1; return ;}
        int mid = (l+r)>>1;
        build(lson);build(rson);push_up(rt);
    }
    int Querymax(int ql,int qr,int rt,int l,int r)
    {
        if(ql<=l && r<=qr) return maxv[rt];
        if(lazy[rt]) push_down(rt);
        int Max=-INF ,mid=(l+r)>>1;
        if(ql<=mid) Max = max(Max,Querymax(ql,qr,lson));
        if(qr>mid) Max = max(Max,Querymax(ql,qr,rson));
        return Max;
    }
    void update(int ql,int qr,int v,int rt,int l,int r)//区间更新
    {
        if(ql>r||qr<l) return;
        if(ql<=l && qr>=r) {lazy[rt]=max(lazy[rt],v),maxv[rt]=max(maxv[rt],v);return;}
        if(lazy[rt]) push_down(rt);
        int mid=(l+r)>>1;
        update(ql,qr,v,lson);update(ql,qr,v,rson);
        push_up(rt);
    }
}tree;
void dfs1(int u,int pre)
{
    size[u]=1;dep[u]=dep[pre]+1;fa[u]=pre;
    int maxson=-1;
    for(int i=0;i<g[u].size();i++)
    {
        int v=g[u][i];
        if(v==pre) continue;
        dfs1(v,u);
        size[u]+=size[v];
        if(size[v]>maxson) maxson=size[v],son[u]=v;
    }
}
void dfs2(int x,int topx)//
{
    top[x]=topx;id[x]=++cnt;rk[cnt]=x;
    if(son[x]!=-1) dfs2(son[x],topx);
    for(int i=0;i<g[x].size();i++)
    {
        int v=g[x][i];
        if(v==fa[x]||v==son[x]) continue;
        dfs2(v,v);
    }
}
int qmax(int x,int y)
{
    int ans=1;
    for(;top[x]!=top[y];x=fa[top[x]])
    {
        if(dep[top[x]]<dep[top[y]]) swap(x,y);//
        ans=max(tree.Querymax(id[top[x]],id[x],1,1,n),ans);
    }
    if(dep[x]>dep[y]) swap(x,y);
    ans=max(tree.Querymax(id[x],id[y],1,1,n),ans);
    return rk[ans];
}
int main()
{
    rd(n);int q;rd(q);
    FOR(i,1,n-1){int u,v;rd(u);rd(v);g[u].push_back(v);}
    mem(son,-1);dep[0]=0;
    dfs1(1,0);cnt=0;dfs2(1,1);
    tree.build(1,1,n);
    while(q--)
    {
        char s[11];scanf("%s",s);int x;rd(x);
        if(s[0]=='C') tree.update(id[x],id[x]+size[x]-1,id[x],1,1,n);//子树即为
        else printf("%d\n",qmax(x,1));//询问路径最大值
    }
    return 0;
}