轻重链剖分
论文鸽说叫 heavy-light decomposition 或 heavy path decomposition .
正确叫法（不是）：
这是真的：
轻重链剖分基本原理
一个节点子树大小最大的儿子叫重儿子 .
节点到重儿子的边叫重边 .
一堆重边叫重链 .
重儿子优先 DFS，于是重链连续，每条链可以拆成若干条重链和杂边 .
每次走轻儿子子树大小至少除以二，于是每条链可以拆成 \(\log\) 条重链，用线段树维护 DFS 序就可以做到 \(\log^2\) .
这就是轻重链剖分的基本原理 .
代码实现（板子）
题面
维护一棵 \(n\) 个点有点权的树，支持
- 换根
- 路径修改
- 子树修改
- 路径和
- 子树和
换根影响
树上两点间路径唯一，于是路径啥事没有
换根对子树的影响可以看 树 社论 的做法，就是拆成子树补啥的 .
于是做完了 .
轻重链剖分
轻重链剖分通过两次 dfs 完成，非常好理解吧 .
整理一下要维护的东西：
- 父亲
- 深度
- 子树大小
- 重儿子
- 所在重链顶端节点（
top） - DFS 序相关
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!
树剖完就是线段树题了qwq
没了
题外话
——《Segment Tree Beats!》
应该是圆方树解决吧 .