题目传送门

一、理解与感悟

1. 无向图就是存两个方向的有向图，比如无向图中两个节点\(a,b\), 我们就保存\(a->b\),同时也保存\(b->a\)，就描述了无向图。

2. 如果是稠密图，用邻接矩阵，就是二维数组，比如 g[i][j],用来记录从i点到j点是不是有边，有则为true,没有由为false;如果边是有权的，那么可以保存边权的值。
   但这么做的缺点是，需要的空间大，因为不管有没有边，都要保存两者之间的关系，而且是双向的关系，100个点要保存10000个数字，空间复杂度太高，一般不太常用。因为稀疏图一般不是每两个节点之间就一定存在边的，而是大部分节点之间是没有边的，所以大量的占用了0x3f3f3f3f,表示两个节点之间距离是无穷大。

3、不管是稠密图，还是稀疏图，都可以用邻接表来存储，其实就是用h数组+链表来存储，其中h数组表示的是N个结点，表示每个结点为出发点的目标点集合。
e[N],ne[N],idx 这三位大神，其实是用数组来模拟存储链表，可以用来保存多个链表，每条链表的头是h[k],表示从节点k出发可以到达的目标点集合。这种用数组模拟链表的方法，也被称为链式前向星。

4、树也是一种图，是一种有向无环图。所有用h数组+链表的方法也可以用来保存树。当然，也可以是多棵树。

5、图的遍历也可以用深度优先遍历和广度优先遍历。树也是一种特殊的图。

6、图的深度优先遍历与广度优先遍历，一般都是只遍历一次，99%只是一次，所以需要记录哪个点是不是走过了，走过了的不要重复走。

7、在树的深度优先遍历过程中，我们是可以顺带返回每个子树的节点数量的。换句话说，因为我们这道题需要知道子树的节点个数，所以，才想到了dfs.

#include<iostream>
#include<algorithm>
#include<cstring>

const int N=100010,M=N*2; //这里认为M条边，一般有2*N条边就算是不错了，够用了。
int h[N],e[M],ne[M],idx;
bool st[N]; //是不是走过了，走过了的不再走。

void add(int a,int b){ 
   e[idx]=b,ne[idx]=h[a],h[a]=idx++; //头插法啊，注意啊，头插法
}

memset(h,-1,sizeof h);

void dfs(int u){
  st[u]=true; //标记一下，已经被搜过了
  for(int i=h[u];i!=-1;i=ne[i]){
         int j=e[i]; 		//找到对应的节点
         if(!s[j]) dfs(j);		//疑问：这里没有地方记录类似于权的东西，
         //那么图的权边是怎么样用邻接表来记录的呢？？
  }
}

6、树的重心
重心定义：重心是指树中的一个结点，如果将这个点删除后，剩余各个连通块中点数的最大值最小，那么这个节点被称为树的重心。

按定义，树的重心只有一个（好像这么说也不准确，比如有两个节点，删除后都能保证删除后，剩余各个连通块中点数的最大值最小，这两个最大值一样大，都是最小）
举个类比的例子，就好理解了，比如十个班级考试，每个班的最大分数，就是每班的第一名成绩，放在一起比较，找出最低的分数，可以知道哪个班级的最高分最低，当然，这可能有相同的存在，比如两个班级的最高分都是95分，那类似就是重心有两个。

知识点：
（1）dfs可以计算出从u节点出发，可以到达的子树中所有节点的个数。
(2) 如果删除节点u,那么整个树剩余的非u家族的部分，就是总个数-以u为起点树的节点个数
(3) dfs(1)就是表示以1为根

C++ 代码

#include <bits/stdc++.h>

using namespace std;

const int N = 100010, M = N * 2;

int n;
int h[N], e[M], ne[M], idx; //h[N]表示有N条单链表的头,e[M]代表每个节点的值,ne[M]代表每个节点的下一个节点号
//答案
int ans = N; //剩余各个连通块中点数的最大值最小,最大不可能超过N,将N设置为初始值
bool st[N]; //是不是走过了

//树和图的存储
void add(int a, int b) {
    //头插法
    e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}


//函数定义：以u为根的子树的节点数量
//dfs有一个特点，可以附加的带回这个子树有多少个节点
int dfs(int u) {
    st[u] = true;   // 标记下当前点被搜索过了
    //以当前u节点为根进行搜索时，会有多少个节点被遍历到，就是以u为根的子树有多少个节点
    int sum = 1, res = 0; //sum从1开始，因为自己这个点算第一个点
    //遍历一下当前点的所有出边(其实就是把这个链条全拉出来)
    for (int i = h[u]; i != -1; i = ne[i]) {
        int j = e[i];
        if (!st[j]) { //没走过
            int s = dfs(j); 	//走
            sum += s;       	//累加的节点数和，这一句和 res=max(res,s)没有关系啊
            //注意，没有关系，它是和 res=max(res,n-sum)有关系啊！
            
            
            res = max(res, s);	//这个节点如果去掉的话，生成的子树节点最多的是多少
        }
    }
    res = max(res, n - sum); //反向建构把它删除后，其它的是不是比由它生成的多
    //哪个方案最少的最大是答案
    ans = min(ans, res);
    return sum;
}

int main() {
    //树的结点数
    cin >> n;
    
    //h节点初始化为-1，这是槽中i节点对应的链表，如果是-1，表示没链表中没有元素，就是没有从i出发的边。
    //同时，-1是链表结束的标识，通过头插法，把-1修改为最后一个元素，也就是结尾。
    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 << endl;
    return 0;
}