给定一颗树，树中包含 n
个结点（编号 1∼n
）和 n−1
条无向边。

请你找到树的重心，并输出将重心删除后，剩余各个连通块中点数的最大值。

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

输入格式
第一行包含整数 n
，表示树的结点数。

接下来 n−1
行，每行包含两个整数 a
和 b
，表示点 a
和点 b
之间存在一条边。

输出格式
输出一个整数 m
，表示将重心删除后，剩余各个连通块中点数的最大值。

数据范围
1≤n≤105

输入样例
9
1 2
1 7
1 4
2 8
2 5
4 3
3 9
4 6
输出样例：
4

#include<bits/stdc++.h>
using namespace std;
int n;

const int N=1e5+5;

vector<int>v[N];

int sz[N];    //当前节点的子树大小

int jie,minn=N;  //jie是重心，minn为重心下的最大子树大小

void dfs(int x,int fath){

    sz[x]=1; //初始化自身大小为1

    int res=0;//用于记录当前节点x的最大子树大小

    for(int i=0;i<v[x].size();i++){ //for循环表示开始遍历x节点的邻接节点

        int y = v[x][i]; //用一个变量y去记录他的邻接接点 并以这个点作为新的节点进行dfs

        if(y==fa) continue;//避免重复访问父节点（防止无限递归）

        dfs(y,x);//此时y的父节点（上一个节点）就为x

        sz[x]+=sz[y];

        res = max(sz[y],res);  //在几个子树中找最大值
    }
    res=max(res,n-sz[x]);//去的子树算完后，剩下来时子树
    if(minn>res)minn=res,jie=x; 
}
int main(){
    cin>>n;
    for(int i=1;i<n;i++){
        int x,y;
        cin>>x>>y;
        v[x].push_back(y);
        v[y].push_back(x);
    }
    dfs(1,0);
    cout << minn;
}

示例树结构

假设输入如下：

5
1 2
1 3
3 4
3 5

对应的树结构为：

1

/ \
2 3
/ \
4 5

则代码的执行逻辑如下

dfs(1,0)
├─ dfs(2,1)
│ └─ sz[2] =1
├─ dfs(3,1)
│ ├─ dfs(4,3)
│ │ └─ sz[4] =1
│ └─ dfs(5,3)
│ └─ sz[5] =1
│ └─ sz[3] =1+1+1=3
└─ sz[1] =1+1+3=5