倍增LCA求解

#include <bits/stdc++.h>
using namespace std;

const int N=100005;
const int M=N*2;

int n, m;
struct Edge{
    int v, ne;
}e[M];
int depth[N], fa[N][17], head[N];
int d[N], ans=0, E=0;

void add(int a, int b){
    e[E].v=b;
    e[E].ne=head[a];
    head[a]=E++;
}

// 倍增LCA
void bfs(){
    memset(depth, 0x3f, sizeof depth);
    depth[0]=0, depth[1]=1;
    queue<int> q;
    q.push(1);
    while(!q.empty()){
        int node=q.front(); q.pop();
        for(int i=head[node]; ~i; i=e[i].ne){
            int v=e[i].v;
            if(depth[v]>depth[node]+1){
                depth[v]=depth[node]+1;
                q.push(v);
                fa[v][0]=node; // v向上跳2^0个单位d到达node
                for(int k=1; k<=16; ++k)
                    fa[v][k]=fa[fa[v][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=head[u]; ~i; i=e[i].ne){
        int v=e[i].v;
        // 分类讨论
        if(v!=father){
            int s=dfs(v, u);
            if(!s) ans+=m;
            else if(s==1) ++ans;
            res+=s;
        }
    }
    return res;
}

int main(){
    cin>>n>>m;
    memset(head, -1, sizeof head);
    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;
        int p=lca(a, b);
        d[a]++, d[b]++, d[p]-=2; // 树上差分
    }
    dfs(1, -1);
    cout<<ans;

    return 0;
}