DFS序就是将树形结构转化为线性结构，用dfs遍历一遍这棵树，进入到x节点有一个in时间戳，递归退出时有一个out时间戳

说人话就是dfs序可以让一个树形结构上面的动态修改转化为线性结构的操作。方便使用线段树或树状数组。

Apple Tree

Link:Apple Tree

Description

There is an apple tree outside of kaka's house. Every autumn, a lot of apples will grow in the tree. Kaka likes apple very much, so he has been carefully nurturing the big apple tree.

The tree has N forks which are connected by branches. Kaka numbers the forks by 1 to N and the root is always numbered by 1. Apples will grow on the forks and two apple won't grow on the same fork. kaka wants to know how many apples are there in a sub-tree, for his study of the produce ability of the apple tree.

The trouble is that a new apple may grow on an empty fork some time and kaka may pick an apple from the tree for his dessert. Can you help kaka?

Input

The first line contains an integer N (N ≤ 100,000) , which is the number of the forks in the tree.
The following N - 1 lines each contain two integers u and v, which means fork u and fork v are connected by a branch.
The next line contains an integer M (M ≤ 100,000).
The following M lines each contain a message which is either
"C x" which means the existence of the apple on fork x has been changed. i.e. if there is an apple on the fork, then Kaka pick it; otherwise a new apple has grown on the empty fork.
or
"Q x" which means an inquiry for the number of apples in the sub-tree above the fork x, including the apple (if exists) on the fork x
Note the tree is full of apples at the beginning

Output

For every inquiry, output the correspond answer per line.
Sample Input

3
1 2
1 3
3
Q 1
C 2
Q 1
Sample Output

3
2

Problem solving:

这道题的意思就是给你一颗树，初始时树上每个节点的权值都为1。然后查询，每次查询可能有两种操作，一种是找到一个节点修改它的值，1变0，0变1。还有一种就是查询以当前点为根的子树的权值和。

因为是动态修改查询的。所以这里我们先用dfs序转化为线性，再用树状数组维护就可以了。

用dfs遍历一遍这棵树，进入到x节点有一个in时间戳，递归退出时有一个out时间戳，易知，每个结点的in和out之间的dfs到的节点就是以x为根的子树中的节点们。所以dfs序得到的两个数组就是代表这个点“控制”的区间。我们再用树状数组维护一下前缀和，查询的时候直接减就好了。具体操作可看代码注释。

Code

#include <iostream>
#include <cstring>
using namespace std;
const int maxn = 1e5 + 10;
#define lowbit(x) (x & (-x))
int n, q, t;
struct node {
    int to, nxt;
} v[maxn << 1];
int head[maxn], cnt;
int tree[maxn];                 //存储树状数组
int vis[maxn];                  //存储每个结点的值
int in[maxn], out[maxn], tim;   //dfs序
void addv(int from, int to)
{
    v[cnt].to = to;
    v[cnt].nxt = head[from];
    head[from] = cnt++;
}//链式前向星存图
void dfs(int x, int fa)
{
    in[x] = ++tim;
    for (int i = head[x]; i != -1; i = v[i].nxt) {
        int mid = v[i].to;
        if (mid == fa) continue;
        dfs(mid, x);
    }
    out[x] = tim;
}//计算dfs序
void add(int x, int val)
{
    for (; x <= n; x += lowbit(x)) tree[x] += val;
}//树状数组单点修改
int query(int x)
{
    int ans = 0;

    for (; x; x -= lowbit(x)) ans += tree[x];
    return ans;
}//树状数组查询
int main()
{
    ios::sync_with_stdio(0);
    while (cin >> n) {
        memset(head, -1, sizeof(head));
        memset(vis, 1, sizeof(vis));
        memset(tree, 0, sizeof(tree));
        cnt = tim = 0;//初始化
        for (int i = 1, u, v; i < n; i++) {
            cin >> u >> v; addv(u, v); addv(v, u);
        }
        dfs(1, -1);
        for (int i = 1; i <= n; i++) add(i, 1); //初始化树状数组
        char op; int q, t;
        cin >> q;
        while (q--) {
            cin >> op >> t;
            if (op == 'C') {
                if (vis[t]) {
                    add(in[t], -1);//in[t]就是t在树状数组所用的序列中的位置
                    vis[t] = 0;
                } else {
                    add(in[t], 1);
                    vis[t] = 1;
                }
            } else {
                cout << query(out[t]) - query(in[t] - 1) << endl;
            }
        }
    }
}

dfs序模板

void dfs(int x, int fa)
{
    in[x] = ++tim;
    for (int i = head[x]; i != -1; i = v[i].nxt) {
        int mid = v[i].to;
        if (mid == fa) continue;
        dfs(mid, x);
    }
    out[x] = tim;
}//计算dfs序

很骚而且挺实用的一种操作。明天把那个lca+dfs序的写一下！

赏