学步园

居然贪心。

先求LCA，都保存好，然后按lca的深度排序，一个个判断，可以取的话将子树都标记了，再看下一个。

#include<iostream>
#include<cstring>
#include<string>
#include<cstdio>
#include<algorithm>
#include<map>
#include<queue>
#include<stack>
#include<cmath>
using namespace std;
struct node
{
    int l,r,top,c;
} p[111111];
vector<int>g[111111];
vector<int>d[111111];
bool vis[111111];
bool vv[111111];
int r[111111];
int f[111111];
int c[111111];
int m,n,ans,num;
void init()
{
    num=0;
    memset(vis,0,sizeof(vis));
    memset(r,0,sizeof(r));
    memset(vv,0,sizeof(vv));
    for(int i=1; i<=n; i++){g[i].clear();d[i].clear();f[i]=i;}
}
int find(int x)
{
    if(f[x]==x)return x;
    f[x]=find(f[x]);
    return f[x];
}
void mark(int u)
{
    vv[u]=1;
    int size=g[u].size();
    for(int i=0; i<size; i++)
    {
        int v=g[u][i];
        if(c[u]>c[v])continue;
        if(vv[v]==1)continue;
        mark(v);
    }
}
void dfs(int u)
{
    vis[u]=1;
    int size=d[u].size();
    for(int i=0; i<size; i++)
    {
        int v=d[u][i];
        if(vis[v])
        {
            int fa=find(v);
            p[num].l=u;p[num].r=v;p[num].top=fa;p[num].c=c[fa];
            num++;
        }
    }
    size=g[u].size();
    for(int i=0; i<size; i++)
    {
        int v=g[u][i];
        if(v==r[u])continue;
        c[v]=c[u]+1;r[v]=u;dfs(v);
    }
    f[u]=r[u];
}
bool cmp(node x,node y)
{
    return x.c>y.c;
}
void solve()
{
    sort(p,p+num,cmp);
    for(int i=0; i<num; i++)
    {
        if(!vv[p[i].l]&&!vv[p[i].r])
        {
            ans++;mark(p[i].top);
        }
    }
}
int main()
{
    int u,v;
    while(scanf("%d%d",&n,&m)!=EOF)
    {
        init();
        for(int i=1; i<n; i++)
        {
            scanf("%d%d",&u,&v);
            g[u].push_back(v);g[v].push_back(u);
        }
        for(int i=0; i<m; i++)
        {
            scanf("%d%d",&u,&v);
            d[u].push_back(v);d[v].push_back(u);
        }
        ans=0;
        c[1]=1;
        r[1]=1;
        dfs(1);
        solve();
        printf("%d\n",ans);
    }
    return 0;
}