模拟 树的重心

C++ 代码

#include <iostream>
#include <cstring>
using namespace std;

const int N = 100010, M = N*2;
int h[N], e[M], ne[M], idx;

int n;
int maximum = 0;
int minimum = N;
int cnt = 1;

bool st[N];

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

void dfs(int u, int m){
    st[u] = true;
    for(int i=h[u]; i!= -1; i = ne[i]){
        int j = e[i];
        if(!st[j] && j!=m){
            cnt++;
            dfs(j, m);
        } 
    }
}

int main(){
    memset(h,-1,sizeof h);
    cin >> n;
    for(int i=1; i<n;++i){
        int a, b;
        cin >> a >> b;
        add(a,b);
        add(b,a);
    }
    for(int i=1; i<n; ++i){
        maximum = 0;
        for(int j=1; j < n; ++j){
            if(i!=j){
                memset(st, false , sizeof st);
                cnt = 1;
                dfs(j, i); // 从结点j开始搜去除了结点i的树
                maximum = maximum < cnt ? cnt : maximum;
                //cout << i << ' ' << j << ' ' << maximum << ' ' << cnt << endl;
            }
        }
        //cout <<i  <<  ' ' << maximum<<endl;
        minimum = minimum > maximum ? maximum : minimum;
    }
    cout << minimum << endl;
}

TLE