dfs序基础+树上差分（树链剖分）
基础
对于一些树上问题，如果不转化就很难求解。可以考虑转化为区间问题。
dfs序
可以发现，如果点
树上差分
普通差分：序列上进行差分。
数上差分：子树上进行差分。
点差分的基础题型：给定一棵树，把
树上差分需要加减四处：
diff[x]++ ;
diff[y]++ ;
diff[Lca]-- ;
diff[fa]-- ;例题
T664766 dfs序基础1
先把，每个点都替换为他的 dfn。
对于修改，用树状数组维护即可，注意，修改的是他的新编号。
最后是查询，用树状数组求，然后减掉多余部分即可。
//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
改变的地方就是需要区间修改，用线段树维护即可。
//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
是区间修改，单点查询，所以可以用树状数组维护即可。
//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
模版题。
求出每个点的差分值后，记得要把整个子树的加起来才是答案。
//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 ;
}