这份Blog将会包括两部分 长链剖分和dsu on tree
我们先讲一些前置知识 $\color{red}{轻重链剖分}$吧
我们一般认为的树链剖分默认为轻重链剖分 主要的思想在于让重链上的dfn序连续 从而将树上的问题转化成几个区间的问题
考虑如何做到这件事情:
在第一次dfs的时候 我们便要去处理出来重儿子 方便第二次去进行剖分 这件事情很$naive$ 就是在dfs的过程中去记录下重儿子的序号
void dfs1(int u,int f)
{
dep[u] = dep[f] + 1;
fa[u] = f;
son[u] = -1;
siz[u] = 1;
for (int i = head[u]; i != -1; i = nxt[i])
{
int v = pnt[i];
if (v == f) continue;
dfs1(v);
siz[u] += siz[v];
if (son[u] == -1 || siz[v] > siz[son[u]]) son[u] = v;
}
}在第二次dfs的时候 优先遍历重儿子 再遍历轻儿子 这样就可以保证重链上的dfn序连续
void dfs2(int u,int tp)
{
top[u] = tp;
dfn[u] = ++cnt;
rnk[cnt] = u;
if (son[u] == -1) return ;
dfs2(son[u],tp);
for (int i = head[u]; i != -1; i = nxt[i])
{
int v = pnt[i];
if (v == fa[u] || v == son[u]) continue;
dfs2(v,v);
}
}很明显这样剖分完了之后 我们做到了重链上dfn序连续 并且注意到 我们这样剖分完会产生$logn$条链 那么我们来看一下树剖之后的小常数求lca
int query(int x,int y)
{
while (top[x] != top[y])
{
if (dep[top[x]] < dep[top[y]]) swap(x,y);
x = fa[top[x]];
}
if (dep[x] > dep[y]) swap(x,y);
return x;
}这样子寻找lca的常数很小倍增留下了泪水
dsu on tree
到这里 我们花了60+行解释了树剖 终于引出第一个主题 dsu on tree
dsu on tree基于的是树剖的思想 让重儿子的贡献直接继承到父亲上 而轻儿子的考虑暴力合并
无论你是logn - logs的推式子大师 还是每次操作后规模减半的毛估估大师 都能发现这个的复杂度是nlogn的 在处理子树问题时 吊打了树上莫队
我们看一下这样一个代码 我们以CF600E为例题 分析一下算法的流程:
void dfs(int u)
{
for (int i = head[u]; i != -1; i = nxt[i])
{
int v = pnt[i];
if (v == fa[u] || v == son[u]) continue;
dfs(v);
}
if (son[u] != -1) dfs(son[u]);
for (int i = head[u]; i != -1; i = nxt[i])
{
int v = pnt[i];
if (v == fa[u] || v == son[u]) continue;
dsu(v,1);
}
tmp[t[col[u]]] -= col[u];
t[col[u]]++;
tmp[t[col[u]]] += col[u];
if (tmp[maxx + 1]) maxx++;
if (!tmp[maxx]) maxx--;
ans[u] += tmp[maxx];
if (u == top[u]) dsu(u,-1);
}这个是在树链剖分之后的一个计算答案的dfs 其中的top fa son这些数组和在树链剖分中的同义
在这个过程中 不难发现的是 我们后遍历了重儿子 这是和树剖不同的地方
原因很简单 我们遍历轻儿子是为了计算轻儿子的答案 而我们的重儿子是直接继承的 所以先遍历的话会影响到轻儿子的答案的计算
于是我们有了这样的一个算法流程:
1.计算轻儿子的答案
2.遍历重儿子继承重儿子的答案
3.将轻儿子的贡献暴力计算
4.加上自己的贡献 计算自己的答案
5.如果自己是某条重链的头 那么自己必然是某个结点的轻儿子了 此时我们需要消除我们这棵子树的贡献
上面代码中的dsu函数是对于子树遍历的 我给出我的计算方式:
void dsu(int u,int k)
{
tmp[t[col[u]]] -= col[u];
t[col[u]] += k;
tmp[t[col[u]]] += col[u];
if (tmp[maxx + 1]) maxx++;
if (!tmp[maxx]) maxx--;
for (int i = head[u]; i != -1; i = nxt[i])
{
int v = pnt[i];
if (v == fa[u]) continue;
dsu(v,k);
}
}这样dsu on tree的算法部分就讲完了
dsu on tree是一个对于子树问题统计的小trick 很少会作为标算使用 但是也有 我这里列举几道可以使用的题目 按照难度排序
强烈推荐用dsu on tree写一下天天爱跑步 写出来的基本都熟练了（
长链剖分
长链剖分相对而言较冷门 但是在优化有深度信息的dp时 是一个可以考虑的trick
长链剖分是将轻重链剖分的siz计算换成了len的计算 及最长的树链长度 看dfs1的代码可能会清晰一点:
void dfs1(int u,int f)
{
son[u] = -1;
for (int i = head[u]; i != -1; i = nxt[i])
{
int v = pnt[i];
if (v == f) continue;
fa[v] = u;
dfs1(v,u);
len[u] = max(len[u],len[v] + 1);
if (son[u] == -1 || len[v] > len[son[u]]) son[u] = v;
}
}此处的len表示的是某结点的子树中最深的结点到达该结点的距离 长链剖分这个trick真的很冷门 这里推荐一道模板题吧CF1009F
这题中很明显存在一个很trivial的dp方程:
我们用dp[i][j]表示i的子树中距离i为j的结点个数 那么显然有这样的转移:
$$dp[i][j]=\sum\limits_{k\in son_i}dp[k][j-1]$$
有这个转移方程 我们有了一个$O(n^2)$的做法 但是看到数据范围 只能绝望地思考优化
考虑用长链剖分来进行转移 大致的思想是直接继承长儿子的状态 然后暴力合并短儿子的状态 这点上和dsu on tree十分相似 但是dsu on tree基于的是重链剖分
在继承长儿子的状态的时候 我们必须要做到$O(1)$ 不然复杂度依然爆炸 总体上有2种方法:
1.使用指针
2.使用vector的O(1)swap
由于我很不喜欢指针 所以一直用的是vector 我这里给出这题的dfs2作参考:
void dfs2(int u,int tp)
{
top[u] = tp;
dfn[u] = ++cnt;
rnk[cnt] = u;
if (son[u] == -1)
{
ans[u] = 0;
dp[u].push_back(1);
return ;
}
dfs2(son[u],tp);
swap(dp[u],dp[son[u]]);
dp[u].push_back(1);
ans[u] = ans[son[u]];
if (dp[u][ans[u]] == 1) ans[u] = len[u];
for (int i = head[u]; i != -1; i = nxt[i])
{
int v = pnt[i];
if (v == fa[u] || v == son[u]) continue;
dfs2(v,v);
for (int k = len[v]; k >= 0; k--)
{
int tmp = k + len[u] - len[v] - 1;
dp[u][tmp] += dp[v][k];
if (dp[u][tmp] > dp[u][ans[u]] || (dp[u][tmp] == dp[u][ans[u]] && tmp > ans[u]))
{
ans[u] = tmp;
}
}
}
}做完了这题之后 建议去做一下湖南集训 谈笑风生 也算是为数不多的可以找到的长链剖分的练习题了吧
结语
无论是长链剖分还是dsu on tree 本质上是直接继承某个儿子的信息然后暴力合并其他的 仍然是一种十分优雅的暴力trick
dsu on tree十分好写 基本上变化的只有一个dsu函数 而长链剖分的实现其实是存在一定的难度的 湖南集训那题我写了超久/kk
考虑树上的深度 或者子树问题时 没有思路的时候大可思考一下这两个trick 会有很多启发的
完结撒花
鄂公网安备 42010202000505 号