莫欺少年穷，修魔之旅在这开始—>算法提高课题解

思路：

1. d 表示差分数组，d[a]++, d[b]++, d[p]-=2, 表示a到b之间的边 + 1
2. 用 bfs 预处理深度和该点跳 2 ^ k 步后的点
3. 用 lca 求两个点的最近公共祖先
4. 用 dfs 求解，如果是 1，则必定有一条非树边满足，如果是 0，则所有非树边都满足

#include<bits/stdc++.h>

using namespace std;

const int N = 100010, M = 200010;

int n,m;
int h[N],e[M],ne[M],idx;
int depth[N],fa[N][17];
int d[N];
int ans;

void add(int a,int b)
{
    e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}

//预处理深度和该点跳 2 ^ k 步后的点
void bfs()
{
    memset(depth,0x3f,sizeof depth);
    depth[0]=0,depth[1]=1;

    queue<int> q;
    q.push(1);

    while(q.size())
    {
        auto t=q.front();
        q.pop();

        for(int i=h[t];~i;i=ne[i])
        {
            int j=e[i];
            if(depth[j]>depth[t]+1)
            {
                //更新深度
                depth[j]=depth[t]+1;
                q.push(j);

                //更新该点跳 2 ^ k 步后的点
                fa[j][0]=t;
                for(int k=1;k<=16;k++) fa[j][k]=fa[fa[j][k-1]][k-1];
            }
        }
    }
}

int lca(int a,int b)
{
    if(depth[a]<depth[b]) swap(a,b);

    //两者跳到同一深度
    for(int k=16;k>=0;k--)
        if(depth[fa[a][k]]>=depth[b])
            a=fa[a][k];

    if(a==b) return a;

    //两个一起跳到最近公共祖先的下面一层
    for(int k=16;k>=0;k--)
        if(fa[a][k]!=fa[b][k])
        {
            a=fa[a][k];
            b=fa[b][k];
        }

    //返回最近公共祖先
    return fa[a][0];
}

int dfs(int u,int father)
{
    int res=d[u];
    for(int i=h[u];~i;i=ne[i])
    {
        int j=e[i];
        if(j!=father)
        {
            int s=dfs(j,u);
            if(!s) ans+=m;
            if(s==1) ans++;

            //差分数组求和
            res+=s;
        }
    }

    //返回该子树的总和
    return res;
}

int main()
{
    cin>>n>>m;

    memset(h,-1,sizeof h);

    for(int i=0;i<n-1;i++)
    {
        int a,b;
        cin>>a>>b;
        add(a,b);
        add(b,a);
    }

    bfs();

    for(int i=0;i<m;i++)
    {
        int a,b;
        cin>>a>>b;

        //a和b的最近公共祖先
        int p=lca(a,b);

        //树上差分
        d[a]++,d[b]++,d[p]-=2;
    }

    dfs(1,-1);

    cout<<ans<<endl;

    return 0;
}