DFS序專題
牛客專題之DFS序
簡介
dfs序: 每個節點在dfs深度優先遍歷中的進出棧的時間序列，也就是tarjan演算法中的dfn數組。
畫個圖理解一下：
這棵樹的dfs序：1 3 2 4 2 5 6 7 6 5 1。
那麼這個序列有什麼用呢？
通過觀察，兩個相同數字之間就是以它為根的子樹, 也就是說，通過dfs序我們可以得到，這個節點第一次進入棧的時間戳\(l_i\)和第一次出棧的時間戳\(r_i\)。之後我們就可以通過\(l_i\)和\(r_i\)操縱這棵樹了。
具體看題：
模板
Military Problem 原CF1006E
題意
你有一棵有\(n\)個節點的樹，有\(q\)次詢問，每次詢問有\((u,k)\)，指從以\(u\)為根的子樹出發先序遍歷到達的第\(k\)個點是哪一個？如果不存在，輸出\(-1\)。
一道模板題。先預處理出每個點的dfs序, 即每個點的\(l_i\)和\(r_i\)。
詢問的時候判斷是否\(l[u] + k – 1 > r[u]\)， 否則輸出\(a[l[u]+k-1]\)就好了。
/*
//ac.nowcoder.com/acm/problem/112932
//codeforces.com/problemset/problem/1006/E
*/
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int mod = 1e9 + 7;
const int maxn = 2e5 + 10;
int a[maxn], cnt = 0;
int l[maxn], r[maxn];
vector<int> G[maxn];
void dfs(int u, int fa){
l[u] = ++cnt;
a[cnt] = u;
for(auto v : G[u]) {
if(fa == v) continue;
dfs(v, u);
}
r[u] = cnt;
}
int main(){
int n, q;
cin >> n >> q;
for(int i = 2; i <= n; i++) {
int u; cin >> u;
G[i].push_back(u);
G[u].push_back(i);
}
dfs(1, 0);
for(int i = 1; i <= q; i++){
int u, k;
cin >> u >> k;
if(l[u] + k - 1 > r[u]) cout << -1 << endl;
else cout << a[l[u] + k - 1] << endl;
}
return 0;
}
選點
題意
有一棵\(n\)個節點的二叉樹，每個節點有權值\(w_i\)，要選盡量多的點，但是得滿足以下限制：
對於任意一棵子樹，都要滿足：
- 如果選了根節點的話，在這棵子樹內選的其他的點都要比根節點的值大
- 如果在左子樹選了一個點，在右子樹中選的其他點要比它小。
思路
讀題後可以得到：根的值< 右子樹的最大值 < 左子樹的最大值, 如果要得到盡量多的點，只需要記錄從根 -> 右子樹 -> 左子樹的dfs序(此處為入棧時間戳\(l_i\))， 在\(l_i\)上找最長上升子序列(沒想到。。)即可。
程式碼
/*
//ac.nowcoder.com/acm/problem/22494
*/
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int mod = 1e9 + 7;
const int maxn = 2e5 + 10;
int a[maxn], tot = 0, cnt;
int l[maxn], r[maxn], w[maxn], ans[maxn];
vector<int> G[maxn];
void dfs(int u){
if(u == 0) return;
a[++tot] = w[u];
dfs(r[u]); dfs(l[u]);
}
int main(){
int n;
cin >> n;
for(int i = 1; i <= n; i++) cin >> w[i];
for(int i = 1; i <= n; i++) cin >> l[i] >> r[i];
dfs(1);
ans[++cnt] = a[1];
// 最長上升子序列貪心O(nlogn)解法
for(int i = 2; i <= n; i++){
if(a[i] > ans[cnt]) ans[++cnt] = a[i];
else{
int t = lower_bound(ans + 1, ans + 1 + cnt, a[i]) - ans;
ans[t] = a[i];
}
}
cout << cnt << endl;
return 0;
}
dfs序+樹狀數組/線段樹
求和
題意
一顆以\(k\)為根有 \(n\) 個節點的樹，每個節點有一個點權\(v_i\)。有\(m\) 次操作
- 1 x y 表示將節點 \(x\)的權值加上 \(y\)
- 2 x 表示求以\(x\)為根的子樹上所有節點(包括\(x\))的和
思路：
通過 dfs 序將一整棵子樹上映射到序列中連續的一段上。問題就變成對數組進行：單點修改，區間查詢。用樹狀數組維護就好了。
程式碼
/*
//ac.nowcoder.com/acm/problem/204871
*/
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
const int maxn = 1e6 + 10;
int l[maxn], r[maxn];
int bits[maxn];
vector<int> G[maxn];
int n, m, k, cnt = 0;
int lowbit(int x){
return x & (-x);
}
void add(int x, int val){
while(x < maxn){
bits[x] += val;
x += lowbit(x);
}
}
int query(int x){
int res = 0;
while(x){
res += bits[x];
x -= lowbit(x);
}
return res;
}
void dfs(int u, int fa){
l[u] = ++cnt;
for(auto v : G[u]){
if(v == fa) continue;
dfs(v, u);
}
r[u] = cnt;
}
int a[maxn], op[maxn], b[maxn], val[maxn];
int main(){
cin >> n >> m >> k;
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(k, 0);
for(int i = 1; i <= n; i++) add(l[i], a[i]);
for(int i = 0; i < m; i++){
int op; cin >> op;
if(op == 1){
int x, y; cin >> x >> y;
add(l[x], y);
}
else{
int x; cin >> x;
cout << (query(r[x]) - query(l[x]-1)) << endl;
}
}
return 0;
}
Propagating tree 原CF383C
題意
一顆以\(1\)為根有 \(n\) 個節點的樹，每個節點有一個點權\(a_i\)。有\(m\) 次操作
- 1 x y 表示將 \(x\) 結點權值 \(+val\) ，\(x\) 的兒子權值 \(-val\)，\(x\) 的孫子們 \(+val\), 以此類推。
- 2 x 表示\(x\)的點權
思路
乍一看是樹狀數組差分，區間修改，單點查詢。但是第一個操作搞不定，仔細觀察後得到\(1\)操作和每個節點的深度奇偶有關。所以只需判斷一下深度，決定修改的值的正負就可以(又沒想到。。。)。
程式碼
/*
//ac.nowcoder.com/acm/problem/110318
*/
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
const int maxn = 1e6 + 10;
int l[maxn], r[maxn];
int bits[maxn];
vector<int> G[maxn];
int n, m, k, cnt = 0;
int a[maxn], dep[maxn];
int lowbit(int x){
return x & (-x);
}
void add(int x, int val){
while(x < maxn){
bits[x] += val;
x += lowbit(x);
}
}
int query(int x){
int res = 0;
while(x){
res += bits[x];
x -= lowbit(x);
}
return res;
}
void dfs(int u, int fa){
l[u] = ++cnt;
dep[u] = dep[fa] + 1;
for(auto v : G[u]){
if(v == fa) continue;
dfs(v, u);
}
r[u] = cnt;
}
int main(){
cin >> n >> m;
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].pb(v);
G[v].pb(u);
}
dfs(1, 0);
// for(int i = 1; i <= n; i++) add(l[i], a[i]);
for(int i = 0; i < m; i++){
int op; cin >> op;
if(op == 1){
int x, y; cin >> x >> y;
if(dep[x] & 1){
add(l[x], y);
add(r[x] + 1, -y);
} else {
add(l[x], -y);
add(r[x] + 1, y);
}
}
else{
int x; cin >> x;
int y = query(l[x]);
if(dep[x] & 1) cout << a[x] + y << endl;
else cout << a[x] - y << endl;
}
}
return 0;
}
[華華和月月種樹]//ac.nowcoder.com/acm/problem/23051)
題意
華華和月月一起維護了一棵動態有根樹，每個點有一個權值。剛開存檔的時候，樹上只有 0 號節點，權值為 0 。接下來三種操作：
- \(1\) \(i\) 表示月月氪金使節點\(i\) 長出了一個新的兒子節點，權值為\(0\)，編號為當前最大編號 \(+1\)（也可以理解為，當前是第幾個操作 \(1\)，新節點的編號就是多少）。
- \(2\) \(i\) \(a\) 表示華華上線做任務使節點 \(i\) 的子樹中所有節點（即它和它的所有子孫節點）權值加 \(a\) 。
- \(3\) \(i\)，華華需要給出 \(i\) 節點此時的權值。
思路
樹狀數組區間更新單點求值。
操作\(1\)可以將新加的點的減去它的父親的權值來使得新加的點值為\(0\)。
程式碼
/*
//ac.nowcoder.com/acm/problem/23051
//blog.nowcoder.net/n/0055f19c0e49422786d7b7981a914709
*/
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
const int maxn = 1e6 + 10;
int l[maxn], r[maxn];
int bits[maxn];
vector<int> G[maxn];
int m, cnt = 0;
int lowbit(int x){
return x & (-x);
}
void add(int x, int val){
while(x <= cnt + 1){
bits[x] += val;
x += lowbit(x);
}
}
int query(int x){
int res = 0;
while(x){
res += bits[x];
x -= lowbit(x);
}
return res;
}
void dfs(int u){
l[u] = ++cnt;
for(auto v : G[u]) dfs(v);
r[u] = cnt;
}
int a[maxn], op[maxn], b[maxn], val[maxn];
int main(){
cin >> m;
for(int i = 0; i < m; i++){
cin >> op[i] >> a[i];
if(op[i] == 2) cin >> b[i];
else if(op[i] == 1){
G[a[i]].pb(++cnt);
b[i] = cnt;
}
}
dfs(0);
// cout << cnt << endl;
for(int i = 0; i < m; i++){
if(op[i] == 1) val[l[b[i]]] -= query(l[a[i]]);
else if(op[i] == 2){
add(l[a[i]], b[i]);
add(r[a[i]] + 1, -b[i]);
}
else cout << val[l[a[i]]] + query(l[a[i]]) << endl;
}
return 0;
}
