题目描述

给定一棵树，树中包含n个结点（编号n-1）和n-1条无向边。
请你找到树的重心，并输出将重心删除后，剩余各个连通块中，点数的最大值。
重心：重心是指树中的一个结点，如果将这个点删除后，剩余各个连通块中点数最大值最小，那么这个结点被称为树的重心。

输入格式

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

输出格式

输出一个整数m，表示重心的所有子树中最大的子树的结点数目。

样例

输入

9
1 2
1 7
1 4
2 8
2 5
4 3
3 9
4 6

输出

4

树与图的搜索

1.树与图使用邻接表进行存储，其中树可以看作为无向图。
2.邻接表形式可以看作是多个单链表，所以形式与链表实现方式类似，不过头指针为数组形式。
3.进行比较的时候，设定一个很大很大数可以设定为0x3f3f3f3f
4.无向图在添加边的时候，要注意是双向添加。
5.进行搜索时，刚开始要手动将最初的状态值设置为true
6.不要忘记初始化，例如初始化头指针数组为-1，并查集中初始化父节点数组。

C++ 代码

邻接表构造，以及搜索

const int N=1e6;

int e[N],ne[N],idx,h[N];
bool sta[N];

//添加一条a->b
void add(int a,int b){
    e[idx]=b;
    ne[idx]=h[a];
    h[a]=idx++;
}

void dfs(int u){
    for(int i=h[u];i!=-1;i=ne[i]){
        int j=e[i];
        cout<<j<<endl;
        if(sta[j]) continue;
        sta[j]=true;
        dfs(j)
    }
}

题解

#include<iostream>
#include<cstring>

using namespace std;

const int N=1e6;

int e[N],ne[N],idx,h[N];
bool sta[N];
int childmax[N];
int n;

void add(int a,int b){
    e[idx]=b;
    ne[idx]=h[a];
    h[a]=idx++;
}

int dfs(int u){
    int childCount=1;
    for(int i=h[u];i!=-1;i=ne[i]){
        int j=e[i];
        if(sta[j]) continue;
        sta[j]=true;
        int temp=dfs(j);
        childCount+=temp;
        if(temp>childmax[u]) childmax[u]=temp;
    }
    if(n-childCount>childmax[u]) childmax[u]=n-childCount;
    return childCount;
}

int main(){
    memset(h,-1,sizeof(h));
    cin>>n;
    for(int i=0;i<n-1;i++){
        int a,b;
        cin>>a>>b;
        add(a,b);
        add(b,a);

    }
    sta[e[0]]=true;
    dfs(e[0]);
    int Min=0x3f3f3f3f;
    int index=0;
    for(int i=1;i<=n;i++){
        if(childmax[i]<Min) Min=childmax[i];

    }
    cout<<Min<<endl;


    return 0;
}