浅谈树上的两个小trick

这份Blog将会包括两部分 长链剖分和dsu on tree 我们先讲一些前置知识 $\color{red}{轻重链剖分}$吧 我们一般认为的树链剖分默认为轻重链剖分 主要的思想在于让重链上的dfn序连续 从而将树上的问题转化成几个区间的问题 考虑如何做到这件事情: 在第一次dfs的时候 我们便要去处理出来重儿子 方便第二次去进行剖分 这件事情很$naive$ 就是在dfs的过程中去记录下重儿子的序号 ```cpp 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序连续 ```cpp 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 ```cpp 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为例题 分析一下算法的流程: ```cpp 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函数是对于子树遍历的 我给出我的计算方式: ```cpp 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 很少会作为标算使用 但是也有 我这里列举几道可以使用的题目 按照难度排序 [CF600E](https://codeforces.com/problemset/problem/600/E) [CF375D](http://codeforces.com/problemset/problem/375/D) [CF570D](http://codeforces.com/problemset/problem/570/D) [CF741D](http://codeforces.com/problemset/problem/741/D) [天天爱跑步](https://loj.ac/problem/2359) 强烈推荐用dsu on tree写一下天天爱跑步 写出来的基本都熟练了（ ## 长链剖分 长链剖分相对而言较冷门 但是在优化有深度信息的dp时 是一个可以考虑的trick 长链剖分是将轻重链剖分的siz计算换成了len的计算 及最长的树链长度 看dfs1的代码可能会清晰一点: ```cpp 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](http://codeforces.com/problemset/problem/1009/F) 这题中很明显存在一个很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作参考: ```cpp 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; } } } } ``` 做完了这题之后 建议去做一下 [长链剖分求k级祖先模板](https://www.luogu.com.cn/problem/P5903) [湖南集训 谈笑风生](https://www.luogu.com.cn/problem/P3899) [POI2014 HOTEL加强版](https://www.luogu.com.cn/problem/P5904) 也算是为数不多的可以找到的长链剖分的练习题了吧 ## 结语 无论是长链剖分还是dsu on tree 本质上是直接继承某个儿子的信息然后暴力合并其他的 仍然是一种十分优雅的暴力trick dsu on tree十分好写 基本上变化的只有一个dsu函数 而长链剖分的实现其实是存在一定的难度的 湖南集训那题我写了超久/kk 考虑树上的深度 或者子树问题时 没有思路的时候大可思考一下这两个trick 会有很多启发的 完结撒花