学习笔记--树上差分-白红宇

学习笔记--树上差分

阅读量：5257 次

发布时间：2019-06-14

本文共 2794 字，大约阅读时间需要 9 分钟。

前言

在做一些树上路径修改&查询相关题目时，有时我们用不着树链剖分，类比于序列上的差分，我们可以进行树上差分，不过情况稍有些不同，分为点值上的差分和边权上的差分两种

点值差分

对树上路径\(path(x,y)\)进行点值差分方法：

\(tag[x]++,tag[y]++,tag[lca(x,y)]-=2\)

询问\(x\)被多少个标记覆盖时进行\(dfs\),将\(x\)所有子树节点\(tag[]\)之和加上\(tag[x]\)即使被覆盖数目

例题：

代码：

#include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             #include 
             
              #include 
              
               #define ll long long #define ri register int using namespace std;const int maxn=50005;const int inf=0x7fffffff;template 
               
                inline void read(T &x){ x=0;int ne=0;char c; while(!isdigit(c=getchar()))ne=c=='-'; x=c-48; while(isdigit(c=getchar()))x=(x<<3)+(x<<1)+c-48; x=ne?-x:x; return ;}int n,k;struct Edge{ int ne,to;}edge[maxn<<1];int h[maxn],num_edge=0;inline void add_edge(int f,int to){ edge[++num_edge].ne=h[f]; edge[num_edge].to=to; h[f]=num_edge; return ;}int cnt=0;int dep[maxn],fa[maxn],son[maxn],top[maxn],dfn[maxn],rnk[maxn],size[maxn];int sum[maxn];int L,R,dta;void dfs_1(int now){ int v; size[now]=1; for(ri i=h[now];i;i=edge[i].ne){ v=edge[i].to; if(v==fa[now])continue; dep[v]=dep[now]+1,fa[v]=now; dfs_1(v); size[now]+=size[v]; if(!son[now]||size[son[now]]
                
                 dep[y])swap(x,y); sum[x]--,sum[fa[x]]--; return ;}int ans=-inf;void dfs_3(int now){ int v; for(ri i=h[now];i;i=edge[i].ne){ v=edge[i].to; if(v==fa[now])continue; dfs_3(v); sum[now]+=sum[v]; } ans=max(ans,sum[now]); return ;}int main(){ int x,y,z; //double st=clock(); read(n),read(k); for(ri i=1;i

边权差分

对树上路径\((x,y)\)进行差分方法：（注意\(x,y\)这里还是节点）

\(tag[x]++,tag[y]++,tag[lca(x,y)]--,tag[fa[lca(x,y)]]--\)

询问\(x\)被多少标记覆盖方法同上,然而注意！！

解决相关问题时不能把\(tag[root]\)算进贡献，因为它没有后继的边

例题：

代码：

#include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             #include 
             
              #include 
              
               #define ll long long #define ri register int using namespace std;const int maxn=100005;const int inf=0x7fffffff;template 
               
                inline void read(T &x){ x=0;int ne=0;char c; while(!isdigit(c=getchar()))ne=c=='-'; x=c-48; while(isdigit(c=getchar()))x=(x<<3)+(x<<1)+c-48; x=ne?-x:x; return ;}struct Edge{ int ne,to;}edge[maxn<<1];int h[maxn],num_edge=0,n,m;inline void add_edge(int f,int t){ edge[++num_edge].ne=h[f]; edge[num_edge].to=t; h[f]=num_edge; return ;}int dep[maxn],fa[maxn],size[maxn],dfn[maxn],sum[maxn],son[maxn],top[maxn];void dfs_1(int now){ int v; size[now]=1; for(ri i=h[now];i;i=edge[i].ne){ v=edge[i].to; if(v==fa[now])continue; fa[v]=now,dep[v]=dep[now]+1; dfs_1(v); size[now]+=size[v]; if(!son[now]||size[son[now]]
                
                 dep[y])swap(x,y); sum[x]-=2; return;}int main(){ int x,y,z; read(n),read(m); for(ri i=1;i