CodeForces 592D Super M

先把没用的边去掉，求出包含m个点的最小树。然后求出最小树的直径就可以得到答案了。

#include <cstdio>
#include <cstring>
#include <vector>
#include<cmath>
using namespace std;

const int maxn=130000;
struct Edge
{
    int u,v;
    int next;
} e[2*maxn];
int tot;
int h[maxn];
bool f[maxn],q[maxn];
int head[maxn];
int n,m;

int st1,st2;
int len;

void add(int a,int b)
{
    e[tot].u=a;
    e[tot].v=b;
    e[tot].next=head[a];
    head[a]=tot;
    tot++;
}

void dfs(int x)
{
    f[x]=1;
    for(int i=head[x]; i!=-1; i=e[i].next)
    {
        if(f[e[i].v]==0)
        {
            dfs(e[i].v);
            if(q[e[i].v]==1) q[x]=1;
        }
    }
}

void Find(int x,int le,int op)
{
    f[x]=1;
    if(op==1)
    {
        if(le>len) len=le,st1=x;
        else if(le==len&&x<st1) st1=x;
    }
    else if(op==2)
    {
        if(le>len) len=le,st2=x;
        else if(le==len&&x<st2) st2=x;
    }

    for(int i=head[x]; i!=-1; i=e[i].next)
    {
        if(q[e[i].u]==0) continue;
        if(q[e[i].v]==0) continue;
        if(f[e[i].v]==0) Find(e[i].v,le+1,op);
    }
}

int main()
{
    scanf("%d%d",&n,&m);
    memset(f,0,sizeof f);
    memset(q,0,sizeof q);
    memset(head,-1,sizeof head);
    tot=0;
    for(int i=1; i<n; i++)
    {
        int u,v;
        scanf("%d%d",&u,&v);
        add(u,v);
        add(v,u);
    }
    for(int i=1; i<=m; i++)
    {
        int x;
        scanf("%d",&x);
        q[x]=1;
    }
    int g;
    for(int i=1; i<=n; i++) if(q[i]==1)
        {
            g=i;
            dfs(g);
            break;
        }
        
    st1=st2=0x7FFFFFFF;
    memset(f,0,sizeof f);
    len=0;
    Find(g,0,1);
    memset(f,0,sizeof f);
    len=0;
    Find(st1,0,2);

    int ans1=min(st1,st2);

    int ans2=0;
    for(int i=0; i<tot; i=i+2)
    {
        if(q[e[i].u]==0) continue;
        if(q[e[i].v]==0) continue;
        ans2=ans2+2;
    }
    ans2=ans2-len;
    printf("%d
%d
",ans1,ans2);
    return 0;
}