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

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

package main

import(
    "fmt"
    "bufio"
    "os"
)

const N=100010

var(
    reader = bufio.NewReader(os.Stdin)
    writer = bufio.NewWriter(os.Stdout)

    n int
    a,b int

    h [N]int // 头结点索引
    e [2*N]int // 节点值，存在多个关联的节点，可能会存在重复的数值
    ne [2*N]int // 节点关系链表
    idx = 1 // 节点值索引
    st [N]bool // 状态记录
)

// 给定一颗树，树中包含n个结点（编号1~n）和n-1条无向边。
// 
// 将 b 挂到 与 a 连接的关系链表中, 插入到表头, 关系如下：
// 9
// 1 2
// 1 7
// 1 4
// 2 8
// 2 5
// 4 3
// 3 9
// 4 6
//
// 链表结构如下：
// h[1] --> ne 4,7,2
// h[2] --> ne 5,8
// h[3] --> ne 9
// h[4] --> ne 6,3,1
// h[5] --> ne 2
// h[6] --> ne 4
// h[7] --> ne 1
// h[8] --> ne 2
// h[9] --> ne 3
func insert(a, b int){
    e[idx] = b
    ne[idx] = h[a]
    h[a] = idx
    idx++
}

var (
    res = N
)

func dfs(k int) int {
    st[k] = true

    sum:=1
    max:=0

    for i:=h[k];i>0;i=ne[i] {
        x:=e[i]

        // 这里会忽略掉已访问过的边
        // 这里只会忽略掉一个节点入口的那个节点
        // 为什么最多只会有一个关联的节点访问过呢？ 可以简单证明
        // 假设 a 连接 b,c, 如果b已经访问过了，c必然没被访问过，否则b和c必然存在连接或间接连接，即存在环，但题目是一个棵树，存在矛盾，故最多只会有一个节点访问过。
        // 忽略掉也没关系，最后会补救
        if !st[x] {
            xsum:= dfs(x)
            sum+=xsum

            if max< xsum{
                max = xsum
            }
        }
    }

    // n - sum 就是忽略掉的那条边连接的节点数
    // 也就是一个点可以知道所有和它连接点的信息
    if n - sum > max {
        max = n - sum
    }

    // 最大连接点数比已知的更少，则当前点更可能为树的重心
    if max < res { 
        res = max
    }

    return sum
}


func main(){
    fmt.Fscan(reader, &n)
    for i:=0;i<n-1;i++{
        fmt.Fscan(reader, &a, &b)
        // 无向边，添加两个方向
        insert(a,b)
        insert(b,a)
    }

    dfs(1)

    fmt.Println(res)
}