专栏文章

dfs序基础+树上差分（树链剖分）

HHhy140516
个人记录参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@minzck1j
此快照首次捕获于
2025/12/02 10:49
3 个月前
此快照最后确认于
2025/12/02 10:49
3 个月前
查看原文

基础

对于一些树上问题，如果不转化就很难求解。可以考虑转化为区间问题。

dfs序

可以发现，如果点 xx 的 dfn 被点 yy 入栈和出栈的时间戳完全覆盖，则 xx 一定在 yy 的一个子树内。

树上差分

普通差分：序列上进行差分。
数上差分：子树上进行差分。
点差分的基础题型：给定一棵树，把 ss 到 tt 的路径的点加上 vv。
树上差分需要加减四处：
CPP
diff[x]++ ;
diff[y]++ ;
diff[Lca]-- ;
diff[fa]-- ;

例题

T664766 dfs序基础1

先把，每个点都替换为他的 dfn。
对于修改，用树状数组维护即可，注意，修改的是他的新编号。
最后是查询，用树状数组求，然后减掉多余部分即可。
CPP
//Code by hhy
#include<bits/stdc++.h>
//#define int long long
#define ull unsigned long long
#define pb push_back
#define fi first
#define se second
#define ll long long
using namespace std ;
const int kMaxN = 1e6 + 5 , MOD = 998244353 , INF = 1e18 ;
struct Edgepr
{
	int u , w ;
};
struct Edgeve
{
	int v , w ;
};
struct node
{
  int x , y , id ;
}Node[kMaxN] ;
int n , m , r ;
int a[kMaxN] , s[kMaxN] , e[kMaxN] ;
long long tre[kMaxN << 1] ;
int tim ;
vector<int> G[kMaxN] ;
inline ll ksm(ll a , ll b)
{
	ll mul = 1 ;
	while(b)
	{
		if(b & 1) mul *= a , mul %= MOD ;
		a *= a ;
		a %= MOD ;
		b >>= 1 ;
	}
	return mul ;
}
inline int lowbit(int x)
{
	return (x & (-x)) ;
}
long long query(int x)
{
	long long ans = 0 ;
	while(x > 0)
	{
		ans += tre[x] ;
		x -= lowbit(x) ;
	}
	return ans ;
}
void update(int x , int vis)
{
	while(x <= n)
	{
		tre[x] += vis ;
		x += lowbit(x) ;
	}
}
void dfs(int u , int fa)
{
	s[u] = ++tim ;
	update(s[u] , a[u]) ;
	for( int i = 0 ; i < G[u].size() ; i++ )
	{
		int v = G[u][i] ;
		if(v == fa) continue ;
		dfs(v , u) ;
	}
	e[u] = tim ;
}
void work()
{
  cin >> n >> m >> r ;
  for( int i = 1 ; i <= n ; i++ ) cin >> a[i] ;
  for( int i = 1 ; i < n ; i++ )
  {
  	int u , v ;
  	cin >> u >> v ;
  	G[u].push_back(v) ;
  	G[v].push_back(u) ;
	}
	dfs(r , 0) ;
	for( int tt = 1 ; tt <= m ; tt++ )
	{
		int op ;
		cin >> op ;
		if(op == 1)
		{
			int t , x ;
			cin >> t >> x ;
			update(s[t] , x) ;
		}
		else
		{
			int t ;
			cin >> t ;
			cout << query(e[t]) - query(s[t] - 1) << "\n" ;
		}
	}
}
signed main()
{
//	freopen(".in" , "r" , stdin) ;
//	freopen(".out" , "w" , stdout) ;
	ios::sync_with_stdio(0) , cin.tie(0) , cout.tie(0) ;
  int t = 1 ;
  // cin >> t ;
  while(t--) work() ;
  return 0 ;
}

T664767 dfs序基础2

改变的地方就是需要区间修改，用线段树维护即可。
CPP
//Code by hhy
#include<bits/stdc++.h>
//#define int long long
#define ull unsigned long long
#define pb push_back
#define fi first
#define se second
#define ll long long
using namespace std ;
const int kMaxN = 1e6 + 5 , MOD = 998244353 , INF = 1e18 ;
struct Edgepr
{
	int u , w ;
};
struct Edgeve
{
	int v , w ;
};
struct node
{
  int x , y , id ;
}Node[kMaxN] ;
int n , m , r ;
int a[kMaxN] , s[kMaxN] , e[kMaxN] ;
long long tre[kMaxN << 2] ;
long long lazy[kMaxN << 2] ;
int num[kMaxN] ;
int tim ;
vector<int> G[kMaxN] ;
inline ll ksm(ll a , ll b)
{
	ll mul = 1 ;
	while(b)
	{
		if(b & 1) mul *= a , mul %= MOD ;
		a *= a ;
		a %= MOD ;
		b >>= 1 ;
	}
	return mul ;
}
#define lson(x) x << 1 
#define rson(x) x << 1 | 1
void push_up(int x)
{
	tre[x] = tre[lson(x)] + tre[rson(x)] ;
}
void push_down(int l , int r , int k)
{
	if(lazy[k])
	{
		int mid = l + r >> 1 ;
		lazy[lson(k)] += lazy[k] ;
		lazy[rson(k)] += lazy[k] ;
		tre[lson(k)] += (mid - l + 1) * lazy[k] ;
		tre[rson(k)] += (r - mid) * lazy[k] ;
		lazy[k] = 0 ;
	}
}
void build(int l , int r , int k)
{
	if(l == r)
	{
		tre[k] = a[num[l]] ;
		return ;
	}
	int mid = l + r >> 1 ;
	build(l , mid , lson(k)) ;
	build(mid + 1 , r , rson(k)) ;
	push_up(k) ;
}
void update(int l , int r , int k , int L , int R , long long c)
{
	if(L <= l && r <= R)
	{
		tre[k] += (r - l + 1) * c ;
		lazy[k] += c ;
		return ;
	}
  	push_down(l , r , k) ;
	int mid = l + r >> 1 ;
	if(L <= mid) update(l , mid , lson(k) , L , R , c) ;
	if(R > mid) update(mid + 1 , r , rson(k) , L , R , c) ;
	push_up(k) ;
}
long long query(int l , int r , int k , int L , int R)
{
	if(L <= l && r <= R)
	{
		return tre[k] ;
	}
	push_down(l , r , k) ;
	int mid = l + r >> 1 ;
	long long res = 0 ;
	if(L <= mid) res += query(l , mid , lson(k) , L , R) ;
	if(R > mid) res += query(mid + 1 , r , rson(k) , L , R) ;
	return res ;
}
void dfs(int u , int fa)
{
	s[u] = ++tim ;
	num[s[u]] = u ;
	for( int i = 0 ; i < G[u].size() ; i++ )
	{
		int v = G[u][i] ;
		if(v == fa) continue ;
		dfs(v , u) ;
	}
	e[u] = tim ;
}
void work()
{
  cin >> n >> m >> r ;
  for( int i = 1 ; i <= n ; i++ ) cin >> a[i] ;
  for( int i = 1 ; i < n ; i++ )
  {
  	int u , v ;
  	cin >> u >> v ;
  	G[u].push_back(v) ;
  	G[v].push_back(u) ;
	}
	dfs(r , 0) ;
	build(1 , n , 1) ;
	for( int tt = 1 ; tt <= m ; tt++ )
	{
		int op ;
		cin >> op ;
		if(op == 1)
		{
			int t , x ;
			cin >> t >> x ;
			update(1 , n , 1 , s[t] , e[t] , x) ;
		}
		else
		{
			int t ;
			cin >> t ;
			cout << query(1 , n , 1 , s[t] , e[t]) << "\n" ;
		}
	}
}
signed main()
{
//	freopen(".in" , "r" , stdin) ;
//	freopen(".out" , "w" , stdout) ;
	ios::sync_with_stdio(0) , cin.tie(0) , cout.tie(0) ;
  int t = 1 ;
  // cin >> t ;
  while(t--) work() ;
  return 0 ;
}

P2982 [USACO10FEB] Slowing down G

是区间修改，单点查询，所以可以用树状数组维护即可。
CPP
//Code by hhy
#include<bits/stdc++.h>
//#define int long long
#define ull unsigned long long
#define pb push_back
#define fi first
#define se second
#define ll long long
using namespace std ;
const int kMaxN = 1e6 + 5 , MOD = 998244353 , INF = 1e18 ;
struct Edgepr
{
	int u , w ;
};
struct Edgeve
{
	int v , w ;
};
struct node
{
  int x , y , id ;
}Node[kMaxN] ;
int n ;
int a[kMaxN] , s[kMaxN] , e[kMaxN] ;
long long tre[kMaxN << 2] ;
long long lazy[kMaxN << 2] ;
int num[kMaxN] ;
int tim ;
vector<int> G[kMaxN] ;
inline ll ksm(ll a , ll b)
{
	ll mul = 1 ;
	while(b)
	{
		if(b & 1) mul *= a , mul %= MOD ;
		a *= a ;
		a %= MOD ;
		b >>= 1 ;
	}
	return mul ;
}
inline int lowbit(int x)
{
	return (x & (-x)) ;
}
long long query(int x)
{
	long long ans = 0 ;
	while(x > 0)
	{
		ans += tre[x] ;
		x -= lowbit(x) ;
	}
	return ans ;
}
void update(int x , int vis)
{
	while(x <= n)
	{
		tre[x] += vis ;
		x += lowbit(x) ;
	}
}
void dfs(int u , int fa)
{
	s[u] = ++tim ;
	for( int i = 0 ; i < G[u].size() ; i++ )
	{
		int v = G[u][i] ;
		if(v == fa) continue ;
		dfs(v , u) ;
	}
	e[u] = tim ;
}
void work()
{
  cin >> n ;
  for( int i = 1 ; i < n ; i++ )
  {
  	int u , v ;
  	cin >> u >> v ;
  	G[u].push_back(v) ;
  	G[v].push_back(u) ;
	}
	dfs(1 , 0) ;
	for( int i = 1 ; i <= n ; i++ )
	{
		int x ;
		cin >> x ;
//		cout << s[x] << " " << e[x] << " " ;
		cout << query(s[x]) << "\n" ;
		update(e[x] + 1 , -1) ;
		update(s[x] , 1) ;
	}
}
signed main()
{
//	freopen(".in" , "r" , stdin) ;
//	freopen(".out" , "w" , stdout) ;
	ios::sync_with_stdio(0) , cin.tie(0) , cout.tie(0) ;
  int t = 1 ;
  // cin >> t ;
  while(t--) work() ;
  return 0 ;
}

P3128 [USACO15DEC] Max Flow P

模版题。
求出每个点的差分值后，记得要把整个子树的加起来才是答案。
CPP
//Code by hhy
#include<bits/stdc++.h>
#define int long long
#define ull unsigned long long
#define pb push_back
#define fi first
#define se second
#define ll long long
using namespace std ;
const int kMaxN = 3e5 + 5 , MOD = 998244353 , INF = 1e18 ;
struct Edgepr
{
	int u , w ;
};
struct Edgeve
{
	int v , w ;
};
struct node
{
  int x , y , id ;
}Node[kMaxN] ;
int n , k ;
int a[kMaxN] , d[kMaxN] , sum[kMaxN] ;
int dep[kMaxN] , dp[kMaxN][25] ;
vector<int> G[kMaxN] ;
inline ll ksm(ll a , ll b)
{
	ll mul = 1 ;
	while(b)
	{
		if(b & 1) mul *= a , mul %= MOD ;
		a *= a ;
		a %= MOD ;
		b >>= 1 ;
	}
	return mul ;
}
void dfs1(int u , int fa)
{
  dep[u] = dep[fa] + 1 ;
  dp[u][0] = fa ;
  for( int i = 1 ; (1 << i) <= dep[u] ; i++ )
  {
    dp[u][i] = dp[dp[u][i - 1]][i - 1] ;
  }
  for( int i = 0 ; i < G[u].size() ; i++ )
  {
    if(G[u][i] != fa) dfs1(G[u][i] , u) ;
  }
}
int lca(int x , int y)
{
  if(dep[x] > dep[y]) swap(x , y) ;
	for( int i = 20 ; i >= 0 ; i-- )
	{
		if(dep[dp[y][i]] >= dep[x]) y = dp[y][i] ;
	}
	if(y == x)
	{
		return x ;
	}
	for( int i = 20 ; i >= 0 ; i-- )
	{
		if(dp[y][i] != dp[x][i]) y = dp[y][i] , x = dp[x][i] ;
	}
	return dp[x][0] ;
}
void dfs2(int u , int fa)
{
	sum[u] = d[u] ;
	for( int i = 0 ; i < G[u].size() ; i++ )
  {
    if(G[u][i] != fa) 
		{
			dfs2(G[u][i] , u) ;
			sum[u] += sum[G[u][i]] ;
		}
  }
}
void work()
{
  cin >> n >> k ;
  for( int i = 1 ; i < n ; i++ )
  {
  	int u , v ;
  	cin >> u >> v ;
  	G[u].push_back(v) ;
  	G[v].push_back(u) ;
	}
	dfs1(1 , 0) ;
	for( int i = 1 ; i <= k ; i++ )
	{
		int x , y ;
		cin >> x >> y ;
		int Lca = lca(x , y) ;
		int fa = dp[Lca][0] ;
		d[x]++ ;
		d[y]++ ;
		d[Lca]-- ;
		d[fa]-- ;
	}
	dfs2(1 , 0) ;
	int maxn = 0 ;
	for( int i = 1 ; i <= n ; i++ ) maxn = max(maxn , sum[i]) ;
	cout << maxn ;
}
signed main()
{
//	freopen(".in" , "r" , stdin) ;
//	freopen(".out" , "w" , stdout) ;
	ios::sync_with_stdio(0) , cin.tie(0) , cout.tie(0) ;
  int t = 1 ;
  // cin >> t ;
  while(t--) work() ;
  return 0 ;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...