AcWing - 나무의 중심 (검색 & 트 리)

제목 링크:https://www.acwing.com/problem/content/description/848/ 시간 / 시간 제한: 1s / 64MB
제목 설명
트 리 를 지정 합 니 다. 트 리 에는 n 개의 노드 (번호 1 ~ n) 와 n - 1 개의 방향 이 없습니다.
트 리 의 중심 을 찾 아 출력 하여 중심 을 삭제 한 후, 나머지 연결 블록 중 포인트 의 최대 값 을 입력 하 십시오.
중심 정의: 중심 은 나무 에 있 는 노드 를 말 합 니 다. 이 점 을 삭제 한 후에 나머지 연결 블록 에서 포인트 의 최대 값 이 가장 작 으 면 이 노드 는 나무의 중심 이 라 고 합 니 다.
입력 형식
첫 줄 은 정수 n 을 포함 하여 나무의 결 점 수 를 나타 낸다.
다음 n - 1 줄 은 각 줄 에 두 개의 정수 a 와 b 를 포함 하고 점 a 와 점 b 전에 한 변 이 존재 한 다 는 것 을 나타 낸다.
출력 형식
중심 을 나타 내 는 모든 하위 트 리 에서 가장 큰 하위 트 리 의 결산 점 수 를 나타 내 는 정수 m 를 출력 합 니 다.
데이터 범위
1≤n≤10^5
입력 샘플
9 1 2 1 7 1 4 2 8 2 5 4 3 3 9 4 6
출력 샘플
4
문제 풀이 의 사고 방향.
제목: 한 가지 점 을 찾 아 숲 에서 가장 큰 나무 노드 를 삭제 하 는 것 이 가장 적다. 그러면 이 점 이 바로 이 나무의 중심 이다. 이 문 제 는 중심 을 구 하 는 것 이다.사고: 정의 에 따라 구 해 중심 은 각 노드 를 각각 삭제 한 후에 형 성 된 숲 에서 가장 큰 서브 나무의 결 점 수 를 비교 하여 이 결 점 수의 가장 작은 결 점 을 나무의 중심 으로 한다.어떤 결점 x 에서 얻 은 자 나 무 를 삭제 하면 두 종류 로 나 눌 수 있 고, 한 종류 x 의 자 나 무 는 전체 나무 에서 x 를 뿌리 로 하 는 자 나 무 를 제거 하 는 부분 이다.첫 번 째 유형의 수량 을 계산 하려 면 x 의 아들 이 몇 명의 자손 이 있 는 지 알 고 두 번 째 유형의 수량 을 계산 하려 면 x 가 몇 명의 자손 이 있 는 지 알 아야 한다.따라서 핵심 적 인 문 제 는 이 나무 에 있 는 모든 결점 에 몇 명의 자손 이 있 는 지 아 는 것 이다. 이것 은 우리 가 재 귀 를 통 해 할 수 있다. 마지막 으로 우 리 는 중심 에 있 는 모든 나무 중에서 가장 큰 자수의 결점 수 를 수출 하면 된다.
Accepted Code:

/* 
 * @Author: lzyws739307453 
 * @Language: C++ 
 */
#include 
using namespace std;
const int MAXN = 1e5 + 5;
const int MAXM = MAXN << 1;
const int inf = 0x3f3f3f3f;
struct AdjTab {
    int u, v;
    AdjTab() {}
    AdjTab(int u, int v) : u(u), v(v) {}
}e[MAXM];
bool vis[MAXN];
int f[MAXN];
int seg = inf, Adj = 0, n;
void Add_Adj(int u, int v) {
    e[++Adj] = AdjTab(f[u], v);
    f[u] = Adj;
}
int DFS(int u) {
    vis[u] = true;
    int ans = 1, res = 0;
    for (int i = f[u]; ~i; i = e[i].u) {
        int v = e[i].v;
        if (!vis[v]) {
            int cnt = DFS(v);
            ans += cnt;
            res = max(cnt, res);
        }
    }
    res = max(res, n - ans);
    seg = min(seg, res);
    return ans;
}
int main() {
    scanf("%d", &n);
    memset(f, -1, sizeof(f));
    for (int i = 1; i < n; i++) {
        int u, v;
        scanf("%d%d", &u, &v);
        Add_Adj(u, v);
        Add_Adj(v, u);
    }
    DFS(1);
    printf("%d
", seg);
    return 0;
}