这里紧承DFS和BFS之后，引出了更加普遍的关于树和图的深度优先搜索和广度优先搜索，在我看来关于树和图的深搜和广搜和前面的深搜和广搜的关系就像是，前者给你一片有限制的空间，你可以往任何地方走，但是你有可能陷入泥潭，此时就需要回溯，我们对于所给定区域的结构是已知的，但我们在走的时候还是义无反顾地去走，后者则是就给了你一幅地图，告诉你往这条路走一定不会陷入泥潭，但你不一定能找到目标（如有更优的看法，欢迎评论哦^_^）
但是在正式介绍我们是怎么对一个树或者图进行深搜之前，我们需要对如何存储一棵树和一个图（有向图或无向图）进行介绍：
我们通常是利用邻接表的方式来存图的，什么是邻接表呢，就是类似于我们在讲哈希时候的拉链法，我们对于每一个节点都开了一条单链表用以存储从当前这个节点能走到的下一个节点。
如图所示，这就是一个邻接表，其实也就是用数组模拟了单链表罢了！
然后我们再次把目光聚焦到树的深度优先搜索上来：
我们先这样理解，如果我们要删掉树上的一个节点，那么树就会分为好几个连通块，分别可以分成是和该节点向下相连的和该节点的父结点，我们就是要去计算这种情况下连通块的最大值的最小值。
因为我们知道这个树本来是连通的，所以我们就递归的枚举每个被删掉的节点，然后去进行比较；
我们先上代码：
#include <iostream>
#include <cstring>
#include <algorithm>
#define maxn 300010
using namespace std;
int h[maxn] , val[maxn] , ne[maxn] ,idx,n,ans = maxn;
bool book[maxn];
void add(int a,int b){
val[idx] = b ; ne[idx] = h[a] ; h[a] = idx++;
}
int dfs(int u){
book[u] = true;
int size = 0 , sum = 0;
for(int i = h[u];i!=-1;i = ne[i]){
int j = val[i];
if(book[j]) continue;
int s = dfs(j);
size = max(size,s);
sum += s;
}
size = max(size,n-sum-1);
ans = min(ans,size);
return sum+1;
}
int main()
{
cin>>n;
memset(h, -1, sizeof h);
for(int i = 0;i<n-1;i++){
int a,b;
cin>>a>>b;
add(a, b); add(b,a);
}
dfs(1);
cout<<ans;
return 0;
}
分析：
·首先，我们可以发现对于存储树和图我们定义了add函数，如果这个图是有向图，我们只需要add一次即可，如果是无向图的话，我们要add两次，因为既可以从a到b，也可以从b到a；
·解释一下这里的size和s和sum和ans：
size指的是如果删掉当前这个u节点之后，图的其他连通块中的元素数量最多的值
s指的是这个点的子树的连通块的值，所以我们会算很多的s去最值
sum指的是这个节点子树元素之和，所以n-sum-1指的是其根节点所在的连通块的元素
ans就是目标答案
我们返回sum+1，指的是告诉这个点的根节点，如果该子节点下连通块的元素数量是（也就是return到上一层的s）
·这道题其实用到了树形dp的思想，我们递归到最下面，相当于我们在dfs子树的基础上自然而然地就得出其父节点的向下的size的最大值，所以整道题其实只遍历了一次所有节点；
------------恢复内容结束------------