【範例】樹壓平 (樹的DFS序)
【題目敘述】https://vjudge.net/problem/HDU-3974
【解題想法】線段樹(Segment Tree) + 樹壓平
目錄
做法(I) 線段樹 + 樹壓平
- 題目是一棵樹：
- 讀入測資時，先用p[ ] 和 vector<int> g[ ] 把樹狀圖存下來。
- Line-74：找出原始樹狀圖的根節點 (下圖例 rt = 2)。
- 從 rt 開始進行樹上的 DFS，找出每位員工 x 在樹上的序位編號。此處的DFS是前序遍歷(preorder traversal)：根 -> 左子樹 -> 右子樹。
- 進出樹狀圖的每個節點時，都有時間戳記(Line-17和Line-21)，進入的時候紀錄一次(in[x])，出來的時候也要紀錄一次(out[x])。
- 每個 in[x] ~ out[x] 區間，代表員工 x 轄下的組織圖(包含 x 及其所有直接/間接部屬)。
- 樹壓平：
- 當樹上的一個節點跟其子樹(subtree)擁有共同性質時(這題是進行相同任務)，把所有人視為同一個群組 (把他們安置在一個「連續區間」)。
- 當原始的樹不是平衡架構，特別是含有長鍊時，利用線段樹來維護資料 (二元樹)，會比較有效率。(但這題的測資太弱分辨不出來。)
- 建立線段樹：
- 查詢員工 x 的任務時，在線段樹上 query(1, 1, N, in[x])。
- 指派任務 y 給員工 x 時，進行線段樹的區間修改 update(1, 1, N, in[x], out[x], y)。
- sum[i]：線段樹上節點 i 的任務編號。
- lz[i]：線段樹上節點 i 尚未往下傳遞的任務編號。
- query( )和update( )之前，都須先做一次 push( )，處理之前留下來的 lazy tag。
#include <iostream>
#include <vector>
#include <cstring>
using namespace std;
const int maxn=50005;
int T, N, u, v, M;
int Case = 1;
char op;
int x, y;
int root, time_stamp;
vector<int> g[maxn];
int p[maxn], in[maxn], out[maxn];
int sum[maxn<<2], lz[maxn<<2];
void dfs(int x){
in[x] = ++time_stamp;
for (auto i: g[x]){
dfs(i);
}
out[x] = time_stamp;
}
void push(int x){
if (lz[x] == -1) return;
sum[x<<1] = sum[x<<1|1] = lz[x];
lz[x<<1] = lz[x<<1|1] = lz[x];
lz[x] = -1;
}
void update(int x, int l, int r, int ql, int qr, int val){
if (ql <= l && r <= qr){
sum[x] = val;
lz[x] = val;
return;
}
push(x);
int mid = (l + r) >> 1;
if (ql <= mid) update(x<<1, l, mid, ql, qr, val);
if (mid+1 <= qr) update(x<<1|1, mid+1, r, ql, qr, val);
}
int query(int x, int l, int r, int pos){
if (l == r){
return sum[x];
}
push(x);
int mid = (l + r) >> 1;
if (pos <= mid) return query(x<<1, l, mid, pos);
else return query(x<<1|1, mid+1, r, pos);
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cin >> T;
while (T--){
cin >> N;
memset(p, 0, sizeof(p));
memset(sum, -1, sizeof(sum));
memset(lz, -1, sizeof(lz));
memset(in, 0, sizeof(in));
memset(out, 0, sizeof(out));
for (int i=0; i<maxn; i++){
g[i].clear();
}
for (int i=0; i<N-1; i++){
cin >> u >> v;
p[u] = v;
g[v].push_back(u);
}
for (int i=1; i<=N; i++){
if (!p[i]) root = i;
}
time_stamp = 0;
dfs(root);
cout << "Case #" << Case++ << ":\n";
cin >> M;
while (M--){
cin >> op;
if (op == 'C'){
cin >> x;
cout << query(1, 1, N, in[x]) << '\n';
} else {
cin >> x >> y;
update(1, 1, N, in[x], out[x], y);
}
}
}
return 0;
}
做法(II) 只有lazy tag
- pa[a] = b：員工 a 的直屬主管是 b。
- vector<int> kid[b]：紀錄主管 b 的屬下們。
- job[x] = y：指派「任務 y」給 「員工 x」。(初始值 -1)
- lazy[x] = y：表示「員工 x」肩負的「任務 y」尚未傳給屬下。(初始值 -1)
- 查詢「員工 x」的任務時，先一層一層回溯(update)其主管的狀態，若主管的lazy tag不是 -1，則先把主管的工作往下傳遞(push)。最後 job[x] 即為正確答案。
- 指派新的「任務 y」給 「員工 x」時，也要先進行update (處理所有上層的lazy tag)，確保未來讀取「員工 x 的屬下們」的狀態時，答案會正確。
#include <iostream>
#include <vector>
#include <cstring>
using namespace std;
const int maxn = 50005;
int t, n, m, a, b, pa[maxn], job[maxn], lazy[maxn];
char C;
vector <int> kid[maxn];
void push(int x){
if (lazy[x] == -1) return;
for (int k:kid[x]){
job[k] = lazy[x];
lazy[k] = lazy[x];
}
lazy[x] = -1;
}
void update(int x){
if (pa[x] != 0){
update(pa[x]);
}
push(x);
return;
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cin >> t;
for (int iter = 1; iter <= t; iter++){
cout << "Case #" << iter << ":\n";
memset(pa, 0, sizeof(pa));
memset(job, -1, sizeof(job));
memset(lazy, -1, sizeof(lazy));
cin >> n;
for (int i = 1; i <= n; i++){
kid[i].clear();
}
for (int i = 1; i < n; i++){
cin >> a >> b;
pa[a] = b;
kid[b].push_back(a);
}
cin >> m;
for (int i = 0; i < m; i++){
cin >> C;
if (C == 'C'){
cin >> a;
update(pa[a]);
cout << job[a] << "\n";
}else{
cin >> a >> b;
update(pa[a]);
job[a] = b;
lazy[a] = b;
}
}
}
}
做法(III) 普通的樹
- Credit: Amy Chou
- p[ ]: 紀錄每位員工的直屬主管。
- {t, task}: 紀錄每位員工被指派的任務及該任務被指派的時間。
- 查詢時，找出員工自己及其所有上層老闆們接受的任務和時間，其中時間最大的任務即是答案。
#include <iostream>
#include <cstring>
using namespace std;
const int maxn=50005;
int T, N, u, v, M;
int Case = 1;
char op;
int x, y;
struct Employee{
int t, task;
} e[maxn];
int p[maxn];
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cin >> T;
while (T--){
cin >> N;
memset(p, 0, sizeof(p));
for (int i=1; i<=N; i++){
e[i].t = 0;
e[i].task = 0;
}
for (int i=0; i<N-1; i++){
cin >> u >> v;
p[u] = v;
}
cout << "Case #" << Case++ << ":\n";
cin >> M;
int time = 0;
while (M--){
cin >> op;
if (op == 'C'){
cin >> x;
int now_t = e[x].t;
int now_task = e[x].task;
while (p[x]){
x = p[x];
if (e[x].t > now_t){
now_t = e[x].t;
now_task = e[x].task;
}
}
if (now_task) cout << now_task << '\n';
else cout << "-1\n";
} else {
cin >> x >> y;
e[x].task = y;
e[x].t = ++time;
}
}
}
return 0;
}