DFS序
前言
回来发现基础反而不会，补基础 QAQ
DFS序实际上是将树这种比较抽象的东西（好像不能这么说）转化为序列上的数的一种手段，便于进行一些能在序列上进行的操作
- DFS序
https://acm.sjtu.edu.cn/w/images/3/35/%E6%A0%91%E7%9A%84dfs%E5%BA%8F%E5%8F%8A%E5%85%B6%E5%BA%94%E7%94%A8%EF%BC%88%E9%97%AB%E9%B8%BF%E5%AE%87%EF%BC%89.pdf
https://blog.csdn.net/LIN452/article/details/51771456
http://www.dbwater.net/2016/08/26/dfsx/
Assign the task - HDU - 3974
题意
给定一棵树，现有两种操作，C x 询问某个节点的价值，Q x y 把价值y覆盖到x及其子树上
思路 —— DFS序 + 线段树
DFS序 + 线段树模板题
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 5e4 + 15;
#define lson l, m, rt << 1
#define rson m + 1, r, rt << 1 | 1
struct edge{
int v, nxt;
};
edge e[N];
int head[N], idg[N];
int tot;
int l[N], r[N], dfs_clock;
int seg[N << 2], lzy[N << 2];
inline void init(){
memset(head, -1, sizeof(head));
memset(seg, -1, sizeof(seg));
memset(idg, 0, sizeof(idg));
memset(lzy, 0, sizeof(lzy));
tot = dfs_clock = 0;
}
inline void addEdge(int u, int v){
e[tot] = edge{v, head[u]};
head[u] = tot++;
idg[v]++;
}
void pushDown(int rt){
if(lzy[rt]){
seg[rt << 1] = lzy[rt];
seg[rt << 1 | 1] = lzy[rt];
lzy[rt << 1] = lzy[rt << 1 | 1] = lzy[rt];
lzy[rt] = 0;
}
}
int query(int idx, int l, int r, int rt){
if(l == r) return seg[rt];
pushDown(rt);
int m = (l + r) >> 1;
if(idx <= m) return query(idx, lson);
else return query(idx, rson);
}
void update(int ql, int qr, int val, int l, int r, int rt){
if(ql <= l && r <= qr){
seg[rt] = val;
lzy[rt] = val;
return;
}
pushDown(rt);
int m = (l + r) >> 1;
if(ql <= m) update(ql, qr, val, lson);
if(m < qr) update(ql, qr, val, rson);
}
void getDfsClock(int u, int pre, int n){
l[u] = ++dfs_clock;
for(int i = head[u]; ~i; i = e[i].nxt){
int v = e[i].v;
if(v == pre) continue;
getDfsClock(v, u, n);
}
r[u] = dfs_clock;
}
int main(){
int t, csn = 1;
scanf("%d", &t);
while(t--){
init();
int n, m;
scanf("%d", &n);
m = n - 1;
while(m--){
int u, v;
scanf("%d%d", &u, &v);
addEdge(v, u);
}
int src; //找根
for(int i = 1; i <= n; i++){
if(!idg[i]){
src = i;
break;
}
}
getDfsClock(src, -1, n);
printf("Case #%d:\n", csn++);
int q;
scanf("%d", &q);
while(q--){
char op[2];
scanf("%s", op);
if(op[0] == 'C'){
int x;
scanf("%d", &x);
printf("%d\n", query(l[x], 1, n, 1));
}else{
int x, y;
scanf("%d%d", &x, &y);
update(l[x], r[x], y, 1, n, 1);
}
}
}
}
Apple Tree - POJ - 3321
题意
给定一棵树，点权开始为1，现在有两种操作： C x 将点x的点权从0变为1或者从1变为0， Q x 询问点x及其子树的价值总和
思路 —— DFS序 + 树状数组
DFS序 + 树状数组模板题
关于那个点权变化的问题，其实只需要另外开个数组记录就行，每次有更改直接异或1
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long ll;
const int N = 1e5 + 15;
#define lson l, m, rt << 1
#define rson m + 1, r, rt << 1 | 1
struct edge{
int v, nxt;
};
edge e[N << 1];
int head[N], tot, dfn;
int tree[N];
int l[N], r[N], a[N];
inline int read() {
char ch = getchar(); int x = 0, f = 1;
while(ch < '0' || ch > '9') {
if(ch == '-') f = -1;
ch = getchar();
} while('0' <= ch && ch <= '9') {
x = x * 10 + ch - '0';
ch = getchar();
} return x * f;
}
inline void init() {
memset(tree, 0, sizeof(tree));
memset(head, -1, sizeof(head));
tot = dfn = 0;
}
inline void addEdge(int u, int v){
e[tot] = edge{v, head[u]};
head[u] = tot++;
}
inline int lowbit(int idx){ return (idx & -idx); }
int getSum(int idx){
int sum;
for(sum = 0; idx > 0; idx -= lowbit(idx)){
sum += tree[idx];
}
return sum;
}
void update(int idx, int val){
while(idx < N){
tree[idx] += val;
idx += (idx & -idx);
}
}
void dfs(int u, int pre){
l[u] = ++dfn;
for(int i = head[u]; ~i; i = e[i].nxt){
int v = e[i].v;
if(v == pre) continue;
dfs(v, u);
}
r[u] = dfn;
}
int main(){
int n;
while(~scanf("%d", &n)){
init();
for(int i = 1; i <= n - 1; i++){
int u = read(), v = read();
addEdge(u, v);
addEdge(v, u);
}
dfs(1, -1);
for(int i = 1; i <= n; i++){
a[i] = 1;
update(l[i], 1);
}
int q = read();
while(q--){
char op = getchar();
int x = read();
if(op == 'Q'){
printf("%d\n", getSum(r[x]) - getSum(l[x] - 1));
}else{
a[x] ^= 1;
if(a[x]) update(l[x], 1);
else update(l[x], -1);
}
}
}
}
New Year Tree - CodeForces - 620E
题意
给定一棵树，树的点给定初始的颜色，现在有两种操作： 1 x y 将x及其子树涂上y色， 2 x 询问x及其子树上有多少种不同的颜色
给定的颜色种类 (1 <= y <= 60)
思路 —— DFS序 + 线段树 + 二进制
如果不带修改，莫队算法完全能够做这题，但是因为涉及修改所以莫队算法不可用
因为给定的颜色种类只有60，因此可以使用二进制数表示每一种颜色，这样子就能用线段树维护了
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long ll;
const int N = 4e5 + 15;
#define lson l, m, rt << 1
#define rson m + 1, r, rt << 1 | 1
struct edge{
int v, nxt;
};
edge e[N << 1];
int head[N], idg[N];
int tot;
int l[N], r[N], dfs_clock;
ll seg[N << 2];
int lzy[N << 2];
int color[N];
int a[N];
inline int read() {
char ch = getchar(); int x = 0, f = 1;
while(ch < '0' || ch > '9') {
if(ch == '-') f = -1;
ch = getchar();
} while('0' <= ch && ch <= '9') {
x = x * 10 + ch - '0';
ch = getchar();
} return x * f;
}
inline void init(){
memset(head, -1, sizeof(head));
tot = dfs_clock = 0;
}
inline void addEdge(int u, int v){
e[tot] = edge{v, head[u]};
head[u] = tot++;
}
void pushUp(int rt){ seg[rt] = seg[rt << 1] | seg[rt << 1 | 1]; }
void pushDown(int rt){
if(lzy[rt]){
seg[rt << 1] = 1LL << lzy[rt];
seg[rt << 1 | 1] = 1LL << lzy[rt];
lzy[rt << 1] = lzy[rt << 1 | 1] = lzy[rt];
lzy[rt] = 0;
}
}
void build(int l, int r, int rt){
lzy[rt] = 0;
if(l == r){
seg[rt] = 1LL << a[l];
return;
}
int m = (l + r) >> 1;
build(lson);
build(rson);
pushUp(rt);
}
ll query(int ql, int qr, int l, int r, int rt){
if(ql <= l && r <= qr) return seg[rt];
pushDown(rt);
int m = (l + r) >> 1;
ll ans = 0;
if(ql <= m) ans |= query(ql, qr, lson);
if(m < qr) ans |= query(ql, qr, rson);
return ans;
}
void update(int ql, int qr, int val, int l, int r, int rt){
if(ql <= l && r <= qr){
seg[rt] = 1LL << val;
lzy[rt] = val;
return;
}
pushDown(rt);
int m = (l + r) >> 1;
if(ql <= m) update(ql, qr, val, lson);
if(m < qr) update(ql, qr, val, rson);
pushUp(rt);
}
void getDfsClock(int u, int pre){
l[u] = ++dfs_clock;
a[dfs_clock] = color[u];
for(int i = head[u]; ~i; i = e[i].nxt){
int v = e[i].v;
if(v == pre) continue;
getDfsClock(v, u);
}
r[u] = dfs_clock;
}
int main(){
int n, q;
while(~scanf("%d%d", &n, &q)){
init();
int m = n - 1;
for(int i = 1; i <= n; i++){
color[i] = read();
}
while(m--){
int u = read(), v = read();
addEdge(u, v);
addEdge(v, u);
}
getDfsClock(1, -1);
build(1, n, 1);
while(q--){
int op = read();
if(op == 2){
int x = read();
ll ret = query(l[x], r[x], 1, n, 1);
int cnt = 0;
while(ret){
cnt++;
ret -= (ret & -ret);
}
printf("%d\n", cnt);
}else{
int x = read(), c = read();
update(l[x], r[x], c, 1, n, 1);
}
}
}
}
