树上点与路径的问题的在线差分解法

Clouder0

发布于 2022-09-23 14:26:59

2710

发布于 2022-09-23 14:26:59

文章被收录于专栏：Coding Is Fun

前言

给出一棵树，在线给出若干条路径，在线询问某个点被多少条路径覆盖。
给出一棵树，在线给出若干个关键点，在线询问某条路径上覆盖了多少个关键点。

这两种问题，有着显而易见的轻重链剖分解法，甚至可以说是轻重链剖分的经典应用。然而，在某些时候，我们认为轻重链剖分 O(\log^2 n) 的代价太大了。那么可以使用树上差分的思想，利用树状数组维护。

点被路径覆盖

给出路径，询问某个点被多少条路径覆盖。考虑路径先全部给出怎么做。一个显然的做法是进行树上差分，将 u \to v 的路径拆分成 u \to lca 与 v \to lca，然后对 fa(lca) 打 -1 标记，对 lca 打 -1 标记，对 u 和 v 打 1 标记即可。随后对全树进行一次搜索即可求出每个点被覆盖多少次。

那么在线如何做呢？求出每个点的 dfs 序，然后使用树状数组维护单点修改、区间查询。对于每条路径，按照树上差分的方法进行单点修改。查询 u 点被多少条路径覆盖，就查询 u 的子树内的权值和。可以这么理解：在树上差分的过程中，u 的子树内的标记，都能在搜索过程中转移到 u 点，而相当于直接求出子树内的标记和来得到该点的值。

例题：[HNOI2016]网络

关键代码：

if(Q[i].type == 2)
{
    int num = Bit::ask(dfn[Q[i].u] + size[Q[i].u] - 1) - Bit::ask(dfn[Q[i].u] - 1);
    if (num == edgenum) q1[++cnt1] = Q[i];
    else q2[++cnt2] = Q[i];
}
else
{
    int t = Q[i].type == 0 ? 1 : -1;
    if(Q[i].val > H[mid])
    {
         Bit::add(dfn[Q[i].u], t), Bit::add(dfn[Q[i].v], t), Bit::add(dfn[Q[i].l], -t);
         if (fa[Q[i].l]) Bit::add(dfn[fa[Q[i].l]], -t);
         q2[++cnt2] = Q[i], edgenum += t;
    }
    else q1[++cnt1] = Q[i];
}

路径覆盖点

给出关键点，询问某条路径覆盖了多少个关键点。

考虑差分怎么做，预处理出 f(i) 代表每个点到根节点的路径上有多少条关键点，随后对于路径 u \to v，可以拆成 u \to lca 与 v \to lca，那么答案就是 f(u) + f(v) - f(lca) - f(fa(lca)).

那么加上在线，一个关键点会对其子树内的点的 f 做出贡献。维护区间修改、单点查询即可。

例题：[CTSC2008] 网络管理

关键代码：

if(Q[i].type <= 2)
{
    if (Q[i].val > H[mid])
    {
        int t = Q[i].type == 1 ? 1 : -1;
        Bit::addrange(dfn[Q[i].u], dfn[Q[i].u] + size[Q[i].u] - 1, Q[i].type == 1 ? 1 : -1);
        if(tvis[Q[i].u] != tim) tsum[Q[i].u] = 0,tvis[Q[i].u] = tim;
        tsum[Q[i].u] += t, q2[++cnt2] = Q[i];
    }
    else q1[++cnt1] = Q[i];
}
else
{
    if (tvis[Q[i].l] != tim) tsum[Q[i].l] = 0, tvis[Q[i].l] = tim;
    int num = Bit::ask(dfn[Q[i].u]) + Bit::ask(dfn[Q[i].v]) - Bit::ask(dfn[Q[i].l]) * 2 + tsum[Q[i].l];
    if (num >= Q[i].val) q2[++cnt2] = Q[i];
    else Q[i].val -= num, q1[++cnt1] = Q[i];
}

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

如有侵权请联系 cloudcommunity@tencent.com 删除

编程算法

本文分享自作者个人站点/博客前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与腾讯云自媒体同步曝光计划，欢迎热爱写作的你一起参与！

编程算法

登录后参与评论

0 条评论

热度