dfs序与树链剖分

dfs序

比如

dfs序为: A B D G H I C E J F

时间戳

时间戳即dfs每次访问到每个节点的时间, 时间从1开始累加
比如上图时间戳为

用处

把树强行搞成连续的
性质:

1. 一个节点的子树上的节点的时间戳, 一定大于这个节点的时间戳且连续
2. 某些链上时间戳也是连续的

树链剖分

树链剖分即把树拆成若干条不相交的链, 分为三种:

1. 重链剖分--常用, \(O(logn)\)
2. 长链剖分--不常用, \(O(\sqrt x)\)
3. 实链剖分--搞LCT
   术语:
   重儿子: 一个结点的所有儿子中大小最大的(只有1个, 如果大小相等就随便取一个)
   轻儿子: 一个节点除了重儿子都是轻儿子
   重链: 从一个轻儿子(根节点也是轻儿子), 一路往重儿子走, 连出的链叫重链
   轻链: 除了重链全是轻链
   剖分好后再dfs一遍标出dfs序就可以了
   注意: dfs标时间戳的时候优先往重儿子走, 轻儿子无所谓
   图示:
   
   黑线两端为重链
   
   标记时间戳

一条重链上的时间戳都是连续的

开始剖分

跑一遍dfs, 标记以下内容:

1. 节点的父亲
2. 节点的重儿子
3. 节点的深度
4. 节点的大小
   再跑一遍dfs, 标记以下内容:
5. 节点权值的dfs序和时间戳
6. 当前节点所在重链的头是谁(最上面的), 头的头是自己
   于是需要这些东西

int fa[N]; // 父亲
int dep[N]; // 深度
int son[N]; // 重儿子
int siz[N]; // 大小
int top[N]; // 头
int dfn[N]; // 时间戳
int w[N]; // 节点权值的dfs序
int tim; // 时间戳计时器
// 维护w数组的线段树
int v[N]; // 存放所有节点的权值

w数组: 比如5号点时间戳为1, 8号为2, 6号为3;那么\(w[1]=5, w[2]=8, w[3]=6\)
第一次dfs:

int fa[N], dep[N], siz[N], son[N];
void dfs1(int u, int f)
{
    fa[u] = f;
    dep[u] = dep[f] + 1;
    siz[u] = 1;
    int maxsize = -1;
    for(int i = h[u]; i != -1; i = ne[i])
    {
        int v = e[i];
        if(v == f) continue;
        dfs1(v, u);
        siz[u] += siz[v];
        if(siz[v] > maxsize)
        {
            maxsize = siz[v];
            son[u] = v;
        }
    }
}

第二次dfs

int tim, dfn[N], top[N], w[N];
void dfs2(int u, int t)
{
    dfn[u] = ++ tim;
    top[u] = t;
    w[tim] = v[u];
    if(!son[u]) return;
    dfs2(son[u], t);
    for(int i = h[u]; i != -1; i = ne[i])
    {
        int j = e[i];
        if(j == fa[u] || j == son[u]) 
            continue;
        dfs2(j, j);
    }
}

P3384

操作3, 4可以用时间戳套一个线段树实现
时间戳是下标, 节点的值是当前下标的值
操作1和操作2就要用树链剖分了

操作3,4:

inline void mson(int x, int z)
{
    change(dfn[x], dfn[x] + siz[x] - 1, z);
}
inline int qson(int x)
{
    return query(dfn[x], dfn[x] + siz[x] - 1);
}

引理: 除根节点外的任何一个节点的父亲节点都一定在一条重链上
证: 父亲节点存在儿子, 所以一定存在重儿子, 所以一定在一条重链上

两个点不在一条重链时, 可以维护2个指针指向2个节点, 不停地让所在链的顶部节点深度较大的指针沿着所在重链往上跳, 一边跳一边在线段树上操作;加完之后p跳到父亲节点;
由引理可知, p仍在一条重链上, 于是循环, 直到跳到同一节点或同一重链

void mchain(int x, int y, int z)
{
    while(top[x] != top[y])
    {
        if(dep[top[x]] < dep[top[y]])
            swap(x, y);
        change(dfn[top[x]], dfn[x], z);
        x = fa[top[x]];
    }
    if(dep[x] > dep[y]) swap(x, y);
    change(dfn[x], dfn[y], z);
}

int qchain(int x, int y)
{
    int res = 0;
    while(top[x] != top[y])
    {
        if(dep[top[x]] < dep[top[y]])
            swap(x, y);
        res += query(dfn(top[x]), dfn[x]);
        x = fa[top[x]];
    }
    if(dep[x] > dep[y])
        swap(x, y);
    res += query(dfn[x], dfn[y]);
    return res;
}