树上差分的两种基本操作

Posted by yjjr's blog on February 6, 2018

转自http://blog.csdn.net/Fine_rose/article/details/77991839


已知路径求被所有路径覆盖的边

  • 首先对已知的这 n 条路径的 起点a终点b 的权值 +1 ,并对 lca(a, b) 的权值 -2
  • 从根节点开始深搜,回溯时将其本身的权值加上所有子节点的权值。
  • 那么满足要求的边就是 权值等于n的节点 与其 父节点 所连的边

dfs代码(使用前向星存图):

void dfs(int x, int father) { // x 为深搜的节点, father 为 x 节点的父节点
    int to;
    for (int i = head[x]; i; i = edges[i].next) {
        to = edges[i].to; // 枚举由 x 节点能够到达的所有的节点

        if (to != father) { // 筛掉 x 节点的父节点
            dfs(to, x); // 深搜 to 节点, 并设置其父节点为x
            value[x] += value[to]; // 累加权值和
        }
    }
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11

已知路径求树上所有节点被路径覆盖次数

  • 对每条路径的 起点a和终点b 的权值 +1 , 对 lca(a, b) 的权值 -1 , 对 lca(a, b)的父节点 权值 -1
  • 从根节点开始深搜,回溯时将其本身的权值加上所有子节点的权值
  • 每个节点的权值既是其被路径覆盖的次数
本文可以转载,但必须附上原文链接,否则你会终生找不到妹子!!!欢迎关注我的CSDN: ahyjjr