论文鸽说叫 heavy-light decomposition 或 heavy path decomposition .
正确叫法(不是):
这是真的:
一个节点子树大小最大的儿子叫重儿子 .
节点到重儿子的边叫重边 .
一堆重边叫重链 .
重儿子优先 DFS,于是重链连续,每条链可以拆成若干条重链和杂边 .
每次走轻儿子子树大小至少除以二,于是每条链可以拆成 \(\log\) 条重链,用线段树维护 DFS 序就可以做到 \(\log^2\) .
这就是轻重链剖分的基本原理 .
LOJ139 树链剖分
维护一棵 \(n\) 个点有点权的树,支持
- 换根
- 路径修改
- 子树修改
- 路径和
- 子树和
树上两点间路径唯一,于是路径啥事没有
换根对子树的影响可以看 树 社论 的做法,就是拆成子树补啥的 .
于是做完了 .
轻重链剖分通过两次 dfs 完成,非常好理解吧 .
整理一下要维护的东西:
top
)Code:
void dfs1(int u) { siz[u] = 1; for (int v : g[u]) { if (v == fa[u]) continue; fa[v] = u; dep[v] = dep[u] + 1; dfs1(v); siz[u] += siz[v]; if (!son[u] || (siz[v] > siz[son[u]])) son[u] = v; } } void dfs2(int u, int t) { top[u] = t; rnk[++cc] = u; dfn[u] = cc; if (!son[u]) return ; dfs2(son[u], t); for (int v : g[u]) if ((v != son[u]) && (v != fa[u])) dfs2(v, v); }
查询修改类似
ll query(int u, int v) { ll ans = 0, fu = top[u], fv = top[v]; while (fu != fv) { if (dep[fu] > dep[fv]){ans += T.query(1, dfn[fu], dfn[u]); u = fa[fu];} else{ans += T.query(1, dfn[fv], dfn[v]); v = fa[fv];} fu = top[u]; fv = top[v]; } if (dfn[u] > dfn[v]) swap(u, v); return ans + T.query(1, dfn[u], dfn[v]); }
可以精简代码です
DFS 序板子,略过 .
Welcome to OI!
——《Segment Tree Beats!》
应该是圆方树解决吧 .