重链剖分

重链剖分

1.重链剖分的板子

void dfsFir(int u, int pre) {
    siz[u] = 1;
    for (auto &[v, w] : edge[u]) {
        if (v == pre) continue;
        dep[v] = dep[u] + 1;
        dfsFir(v, u);
        val[v] = w;
        siz[u] += siz[v], fa[v] = u;
        if (siz[son[u]] < siz[v]) son[u] = v;
    }
}
//其中这里的seg[i]表示线段树上的i位置对应在树上的位置
void dfsSec(int u, int tp) {
    dfn[u] = ++timer, seg[timer] = u, top[u] = tp;
    if (son[u]) dfsSec(son[u], tp);
    for (auto &[v, w] : edge[u]) {
        if (v == fa[u] || v == son[u]) continue;
        dfsSec(v, v);
    }
}

2.把边权转移到点权上

原题链接

解：对于$(u,v)$这条边，其中边权为$w$，我们该如何把这条边转移到点权上呢？只需要让深度大的点存这个边权即可。

例如在上图中，假设以1为根节点，则$(1,2)$的这条边权转换为2的点权；同理$(3,4)$的边权也可以转换为4的点权

那么我们在维护边权信息的时候与点权时有什么不同呢？

1.对于$l$到$r$路径上的边权都$+val$的情况，我们可以把他转换为$l$到$r$路径上的点权都$+val$，之后对于$lca(l,r)$节点$-val$。

为什么最后要减去？因为$lca(l,r)$代表的边权是$(fa[lca],lca)$，并不在$l$到$r$的路径上。

2.对于查询$l$到$r$路径上的边权和，与1同理，我要的答案就是$l$到$r$的点权和，再减去$lca(l,r)$的点权