树上差分（B站视频）

#include<bits/stdc++.h>
#define eb emplace_back
using namespace std;
const int N=5e4+10;
vector<int>G[N];
int dep[N],D,st[N][20];
void dfs(int x,int xfa)
{
    dep[x]=dep[xfa]+1;
    st[x][0]=xfa;for(int i=1;i<=D;++i) st[x][i]=st[st[x][i-1]][i-1];
    for(auto y:G[x])if(y!=xfa) dfs(y,x);
}
int LCA(int x,int y)
{
    if(dep[x]<dep[y])swap(x,y);
    for(int i=D;i>=0;--i)if(dep[st[x][i]]>=dep[y])x=st[x][i];
    if(x==y) return x;
    for(int i=D;i>=0;--i)if(st[x][i]!=st[y][i])x=st[x][i],y=st[y][i];
    return st[x][0]; 
}
int a[N],d[N];
void DP(int x,int xfa)
{
    a[x]=d[x];
    for(auto y:G[x])if(y!=xfa)
    {
        DP(y,x);
        a[x]+=a[y];
    }
}
int main()
{
    int n,m;scanf("%d%d",&n,&m);
    for(int i=1,x,y;i<n;++i)
    {
        scanf("%d%d",&x,&y);
        G[x].eb(y);
        G[y].eb(x);
    }
    dep[0]=0;D=log2(n);dfs(1,0);
    memset(d,0,sizeof(d));
    for(int i=1,x,y;i<=m;++i)
    {
        scanf("%d%d",&x,&y);
        int lca=LCA(x,y);
        d[x]++;d[y]++;d[lca]--;d[st[lca][0]]--;
    }
    DP(1,0);
    int ans=0;for(int i=1;i<=n;++i)ans=max(ans,a[i]);
    printf("%d\n",ans);
    return 0;
}