ACdream 1015 Double Kings

假设第一个人选的点为P，并且当作根，那么第二个人选的最优情况必然是根p连着的那些点中的一个。然后枚举一下P即可。

#pragma comment(linker, "/STACK:1024000000,1024000000")
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<vector>
#include<map>
#include<set>
#include<queue>
#include<stack>
#include<iostream>
using namespace std;
typedef long long LL;
const double pi=acos(-1.0);
void File()
{
    freopen("D:\in.txt","r",stdin);
    freopen("D:\out.txt","w",stdout);
}

const int maxn=50000+10;

int h[maxn],sz,n;
struct Edge
{
    int u,v,nx;
}e[2*maxn];

int sum[maxn],mx[maxn];
bool f[maxn];

void add(int a,int b)
{
    e[sz].u=a; e[sz].v=b; e[sz].nx=h[a]; h[a]=sz++;
}

void dfs(int x)
{
    f[x]=1; sum[x]=1;
    for(int i=h[x];i!=-1;i=e[i].nx)
    {
        if(f[e[i].v]==1) continue;
        dfs(e[i].v);
        sum[x]=sum[x]+sum[e[i].v];
        mx[x]=max(mx[x],sum[e[i].v]);
    }
}

int main()
{
    while(~scanf("%d",&n))
    {
        sz=0; memset(h,-1,sizeof h); memset(f,0,sizeof f);
        for(int i=1;i<=n-1;i++)
        {
            int u,v; scanf("%d%d",&u,&v);
            add(u,v); add(v,u);
        }
        memset(sum,0,sizeof sum);
        memset(mx,0,sizeof mx);
        dfs(1);
        int ans=0;
        for(int i=1;i<=n;i++)
        {
            int x1=n-sum[i], x2=mx[i];
            int da=max(x1,x2);
            ans=max(ans,n-da);
        }
        printf("%d
",ans);
    }
    return 0;
}