线段树之dfs序(HDU-3974)
线段树之dfs序(HDU-3974)
一、什么是dfs序
主要作用:将一个树状的结构转换成线性的结构。
它按照 dfs 深度优先的方式遍历这课树,记录下每个节点入栈与出栈的时刻,这个时刻通过一个全局变量 cnt/tot 递增控制,入栈时刻记录在 Left 数组中,出栈时刻记录在 Right 数组中。
二、线段树+dfs序
线段树在建树的时候需要的是一个线性的序列来表示区间,而不能对树状的数组进行建树,建树是后面其他基本操作的基础。因而当我们需要在一个树上频繁地进行修改结点或者查询结点,那么需要使用线段树来解决,第一步就是要用 dfs 序的方法把树状的数组转换成一个线性的数组。
例题:HDU - 3974 Assign the task
题目大意:公司中存在上下级关系,除了 leader 之外每个员工都有一个自己的直接上司。公司中会分配任务,一个人得到任务后,他所有的下属(如果存在的话)都将放弃之前的任务开始执行这个任务。现在要求某个员工当前在做什么任务。
这道题目的原始题面很明显地引导我们使用线段树来解决这个问题,而题目中的上下属关系形成了一颗树,不可以直接使用线段树来解决。因此需要先使用 dfs 序来转换成线性数组,之后就是普通的线段树操作:区间修改以及单点查询。
参考代码:
// dfs序+线段树 记录!
#include<cstdio>
#include<algorithm>
#include<vector>
#include<cstring>
#include<iostream>
using namespace std;
const int maxn = 5e4+7;
int n, m, ans;
vector<int> adj[maxn]; // 用来保存每个节点的所有孩子
int Left[maxn], Right[maxn];
int cnt[maxn];
struct Node {
int left, right;
int w;
int f;
}tree[4*maxn];
void build(int k, int l, int r){
tree[k].left = l;
tree[k].right = r;
tree[k].f = -1;
tree[k].w = -1;
if(l == r){
return;
}
int mid = (l+r)/2;
build(2*k, l, mid);
build(2*k+1, mid+1, r);
}
void down(int k){
if(tree[k].left == tree[k].right) return;
tree[2*k].w = tree[k].f;
tree[2*k+1].w = tree[k].f;
tree[2*k].f = tree[k].f;
tree[2*k+1].f = tree[k].f;
tree[k].f = -1;
}
// 根据dfs扫描的顺序将“树状”的数组转变成“线状”的数组
int dfs(int u) {
Left[u] = ++m;
for (int i = 0; i < adj[u].size(); i++) {
int v = adj[u][i];
dfs(v);
}
Right[u] = m;
}
void change_interval(int k, int l, int r, int task) {
if(tree[k].left >= l && tree[k].right <= r) {
tree[k].w = task;
tree[k].f = task;
return;
}
if(tree[k].f != -1) down(k);
int mid = (tree[k].left+tree[k].right)/2;
if (l <= mid) change_interval(2*k, l, r, task);
if (r > mid) change_interval(2*k+1, l, r, task);
}
void ask_point(int k, int x) {
if (tree[k].left == tree[k].right){
ans = tree[k].w;
return;
}
if(tree[k].f != -1) down(k);
int mid = (tree[k].left+tree[k].right)/2;
if (x <= mid) ask_point(2*k, x);
else ask_point(2*k+1, x);
}
int main() {
int T,kase = 1;
scanf("%d", &T);
while(T--) {
int u,v;
scanf("%d", &n);
for (int i = 1; i <= n; i++){
adj[i].clear();
}
memset(cnt, 0, sizeof(cnt));
for (int i = 1; i < n; i++) {
scanf("%d%d", &u, &v);
adj[v].push_back(u);
cnt[u]++;
}
// 找根并构造dfs序
for (int i = 1; i <= n; i++) {
if(!cnt[i]) {
m=0;
memset(cnt, 0, sizeof(Left));
memset(cnt, 0, sizeof(Right));
dfs(i);
break;
}
}
build(1, 1, m);
scanf("%d", &m);
char option[3];
printf("Case #%d:\n", kase++);
for (int i = 0; i < m; i++) {
scanf("%s", option);
if (option[0] == 'C') {
scanf("%d", &u);
ans = 0;
ask_point(1, Left[u]);
printf("%d\n", ans);
} else {
scanf("%d%d", &u, &v);
change_interval(1, Left[u], Right[u], v);
}
}
}
}
【END】感谢观看!