学习笔记--树上差分

前言

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

点值差分

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

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

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

例题：https://www.luogu.org/problemnew/show/P3128

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
#include <iostream>
#include <vector>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <cmath>
#include <ctime>
#include <algorithm>
#define ll long long 
#define ri register int 
using namespace std;
const int maxn=50005;
const int inf=0x7fffffff;
template <class T>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]]<size[v])son[now]=v;
       }
       return ;
} 
void dfs_2(int now,int t){
       int v;
       top[now]=t,dfn[now]=++cnt,rnk[cnt]=now;
       if(!son[now])return ;
       dfs_2(son[now],t);
       for(ri i=h[now];i;i=edge[i].ne){
             v=edge[i].to;
             if(v==fa[now]||v==son[now])continue;
             dfs_2(v,v);
       }
       return ;
}
void update_lca(int x,int y){
        while(top[x]!=top[y]){
                if(dep[top[x]]<dep[top[y]])swap(x,y);
                x=fa[top[x]];
        }
        if(dep[x]>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<n;i++){
             read(x),read(y);
             add_edge(x,y);
             add_edge(y,x);
     }  
     dep[1]=1,fa[1]=0;
     dfs_1(1);
     dfs_2(1,1);
     for(ri i=1;i<=k;i++){
             read(x),read(y);
             sum[x]++,sum[y]++;
             update_lca(x,y);
     }
     //double ed=clock();
     dfs_3(1);
     printf("%d\n",ans);
     //printf("%lf\n",ed-st);
     return 0;
}

边权差分

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

$tag[x]++,tag[y]++,tag[lca(x,y)]—,tag[fa[lca(x,y)]]—$

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

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

例题：http://poj.org/problem?id=3417

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
#include <iostream>
#include <vector>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <cmath>
#include <ctime>
#include <algorithm>
#define ll long long 
#define ri register int 
using namespace std;
const int maxn=100005;
const int inf=0x7fffffff;
template <class T>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]]<size[v])son[now]=v;
	}
	return ;
}
void dfs_2(int now,int t){
	int v;
	top[now]=t;
	if(!son[now])return ;
	dfs_2(son[now],t);
	for(ri i=h[now];i;i=edge[i].ne){
		v=edge[i].to;
		if(v==fa[now]||v==son[now])continue;
		dfs_2(v,v);
	}
}
int ans;
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];
	}
	//cout<<sum[now]<<endl;
	if(now!=1&&sum[now]==0)ans+=m;
	else if(now!=1&&sum[now]==1)ans++; 
	return ;
}
void update_path(int x,int y){
	while(top[x]!=top[y]){
		if(dep[top[x]]<dep[top[y]])swap(x,y);
		x=fa[top[x]];
	}
	if(dep[x]>dep[y])swap(x,y);
	sum[x]-=2;
	return;
}
int main(){
	int x,y,z;
	read(n),read(m);
	for(ri i=1;i<n;i++){
		read(x),read(y);
		add_edge(x,y);
		add_edge(y,x);
	}
	fa[1]=0,dep[1]=1;
	dfs_1(1);
	dfs_2(1,1);
	for(ri i=1;i<=m;i++){
		read(x),read(y);
		sum[x]++,sum[y]++;
		update_path(x,y);
	}
	dfs_3(1);
	printf("%d\n",ans);
	return 0;
}

例题待填坑

  • 货车运输

  • 天天爱跑步