最小森林

题目

题目描述

世上本没有路的，走的人多了，也便变成了路。
——鲁迅

Dev-XYS学长决定在一棵树上散步。

这是一棵一棵$n$个节点的树，Dev-XYS学长在树上走出一条路径（不能经过重复的点），由于Dev-XYS学长走得过快，他路过的点及与这些点相邻的边全都被踩坏了，于是这棵树被去掉一条路径，变成了一个“森林”。

为了回收资源，金企鹅学长跟在Dev-XYS学长后面做清理工作。已知企鹅学长只需回收“森林”中节点数最多的那一棵树，他的“辛苦度”是这一棵树的节点个数。

作为企鹅学长“在OI学术相关方面的真爱”，Dev-XYS学长非常心疼辛勤工作的企鹅学长，他希望走出一条最好的路径，使得企鹅学长“辛苦度”最低。

给出一棵树，求最小“辛苦度”。

输入

第1行：一个整数$n$，表示节点个数。
第2~n行：每行两个整数$u$、$v$, 表示$u$、$v$之间有一条边。

输出

一行，一个整数$x$，表示最小辛苦度。

样例

样例输入

5
1 2
2 3
2 4
4 5

样例输出

1

样例解释

Dev-XYS学长可以从1号节点走到5号节点，这样森林中只剩下3号节点，企鹅学长只需回收这棵只有一个节点的树即可。

数据范围

$1 \le n \le 10^6$

提示

这可能是全场最水的题。

#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <iostream>
using namespace std;
const int N = 1000005, INF = 0x3f3f3f3f;
int n;
int ecnt, adj[N], nxt[2*N], go[2*N];
int g[N], f[N], size[N];
void add(int u, int v){
    go[++ecnt] = v;
    nxt[ecnt] = adj[u];
    adj[u] = ecnt;
}
void dfs(int u, int pre){
    size[u] = 1, f[u] = INF;
    int v, son1 = 0, son2 = 0;
    for(int e = adj[u]; e; e = nxt[e])
        if((v = go[e]) != pre){
            dfs(v, u);
            size[u] += size[v];
            f[u] = min(f[u], f[v]);
            if(size[v] >= size[son1])
                son2 = son1, son1 = v;
            else if(size[v] > size[son2])
                son2 = v;
        }
    g[u] = max(size[son2], g[son1]);
    f[u] = min(f[u], max(max(g[son1], g[son2]), n - size[u]));
}
int main(){
    scanf("%d", &n);
    for(int i = 1, u, v; i < n; i++)
        scanf("%d%d", &u, &v), add(u, v), add(v, u);
    dfs(1, 0);
    printf("%d\n", f[1]);
    return 0;
}