再谈树上DFS
树上DFS
树上DFS，就是树上深度优先搜索，该算法通常跟回溯算法一起运用。 其时间复杂度为O(log n）空间复杂度为O（n）.
我将在以下几个方面来向大家讲述：
0.树的名词
1.树上DFS的特性；
2.树上DFS的常用题目；
3.树上DFS的常用写法；
4.树上DFS的常用思路与技巧
0.树的名词及特性
（写给新手，神牛可以跳过）名词：
树：一种特殊的图，这种图像一颗倒过来的树，因此得名。
父亲节点：相对于子节点，若A节点在它下面且A节点与这个节点有边相连，则称这个节点是A的父亲节点。
子节点：相对于父亲节点，若A节点在它上面且A节点与这个节点有边相连，则称这个节点是A的子节点。、
根节点：没有父亲的节点。
内部节点：有父亲也有儿子的节点。
叶子节点：没有儿子的节点。
子树：以某一内部节点为根节点的一棵树。特性：
每一个点只有一个父亲。
一个点到另一点有且只有一条边。
1.树上DFS的特性
树上DFS有如下特性：
1.每个点只有一个父亲（即每个点只会有一次搜索机会）
2.无向（可以从根/叶子节点搜）
3.每个点会有多个儿子（要进行回溯）
2.树上DFS的常用题目
一般来讲，不会超过一下几点：
1.连通块问题；
2.题目中已经明确提到了树的问题;
3.已经有标签的问题。
4.没有上述条件，但有说明树的基础特征的问题。
注：上述第4条中，树的基础特征一般指：从某点到某点有一条无向边的问题。
上述几点是一些判断标准，并不是最后标准，需要各位自己审题！
3.树上DFS的常用写法
1.定义结构体：struct tree{int son（儿子数量）,fa(父亲),sons[1000](具体的儿子是谁）}q[11000];
2.函数：dfs(int x,int last(来源于......）) {(函数中常有向下递归的语句)}
3.回溯（消除递归影响，通常会写在函数中）
4.主函数（输入，调用，输出，结束）
4.树上DFS的常用思路与技巧
“授人以鱼不如授人以渔”，树上DFS很抽象，所以思路与技巧很重要。
为了避免TLE，我们通常采用搜索一遍的方法，这样会很快，这也是为什么有一个last变量，就是因为要提高速度。
题目通常不会告诉我们根节点编号，所以要我们自己去找，其实这也很简单：if（q[i].fa==0）一条语句就可以了。这是因为，根节点没有父亲，所以fa会为初始值0.
但还有一种方法，树可以从下往上搜，即从叶子节点遍历到根节点.
关于这种方法，笔者并不推崇。叶子节点有很多个，大大减少了搜索的稳定性与速度性，这违背了我们用DFS的初衷——对，快，准。
关于树上DFS算法，要说的都说完了。
最后，希望KKKsc03接受我的投稿！
Tanyq265
写于2023/6/10 11:06