f题

路径可以拆成两条链的合成，我们枚举两条链的交点

siz[i]表示以i为根的子树大小

维护dp[i]表示，当i作为链首时，以i为根往下走一条路时的最大连通块的size

我们设first为i的第1大儿子.second为第二大儿子,third为第三大儿子

如何维护dp[i]?

假设我们现在在第i个结点,我们肯定贪心地去消掉第一大儿子的size，所以我们接下来一步会往第一大儿子走，此时dp[i] = max(dp[first] , siz[second])，要么继承最大儿子的答案，要么取第二大儿子的size

dp[i]只是维护好了单链，现在考虑两条链（即路径） 我们考虑i作为两条链的交点，那么我们现在因为有两条链，所以会贪心地去消掉前两大的儿子siz，同时注意第三大儿子的siz消不了，以及路径外面的连通块也要考虑即n-siz[i]部分，所以dp[first],dp[second],siz[third],n-siz[i]四个取最大

则ans = (max ( max(dp[first],dp[second]) , siz[third]) , n-siz[i] ) ，枚举i即可

#include <cmath>
#include <cstring>
#include <string>
#include <algorithm>
#include <map>
#include <list>
#include <queue>
#include <vector>
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <deque>
#include <set>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define _for(i,a,b) for(int i=(a) ;i<=(b) ;i++)
#define scd(v) scanf("%d",&v)
#define scdd(a,b) scanf("%d %d",&a,&b)
#define endl "\n"
#define IOS ios::sync_with_stdio(false),cin.tie(0)
#define pb push_back
#define all(v) v.begin(),v.end()
#define mst(v,a) memset(v,a,sizeof(v))
#define ls p<<1
#define rs p<<1|1
#define int long long
#define inf 0x7f7f7f7f
#define fi first
#define se second
#define pii pair<int , int >
#define ls p<<1
#define rs p<<1|1
#define lson p<<1,l,mid
#define rson p<<1|1,mid+1,r
#define AC return 0
const int N = 1e6 + 100;
const int mod = 1e9 + 9;
int n, m, k;
int ans = inf;
struct ty
{
    int t, next;
}edge[N<<1];
int head[N], tot;
void add(int x, int y)
{
    edge[++tot].t = y;
    edge[tot].next = head[x];
    head[x] = tot;
}
struct T
{
    int fi, se, thi, dp;//第1,2,3大儿子，当前点作为链首时最大子树size
}tr[N];
int siz[N];
void dfs(int x, int fa)
{ 
    siz[x] = 1;
    int max1 = 0, max2 = 0, max3 = 0;
    
    for (int i = head[x]; i; i = edge[i].next)
    {
        int y = edge[i].t;
        if (y == fa) continue;
        dfs(y, x);
        siz[x] += siz[y];
        //维护前三大儿子
        if (siz[y] >= siz[max1]) max3 = max2, max2 = max1, max1 = y;
        else if (siz[y] >= siz[max2]) max3 = max2, max2 = y;
        else if (siz[y] >= siz[max3]) max3 = y;
    }
    tr[x].fi = max1, tr[x].se = max2, tr[x].thi = max3;
    //当前点作为链首时，贪心地去走第一大儿子,所以此时dpi为dp[first_son]和siz[second_son]取最大值
    tr[x].dp = max(tr[max1].dp, siz[max2]);
    //更新ans
    //x作为路径两条链的交点
    //n-siz[x]即路径外面的部分
    //dp[max1]和dp[max2]取大，因为作为交点，贪心地往前两大儿子走
    //以及第三大儿子走不了，也需要包含进去取最大
    //上面四个部分取最大
    ans = min(ans, max(max(max(tr[max1].dp, tr[max2].dp), siz[max3]), n - siz[x]));
}
signed main()
{
    // freopen("data.txt","r",stdin);
    IOS;
    cin >> n;
    _for(i, 1, n-1)
    {
        int x, y; cin >> x >> y;
        add(x, y); add(y, x);
    }
    dfs(1,0);
    cout << max(1ll , ans) << endl;
    AC;
}