树上差分题解

用个深搜

#include<iostream>
#include<vector>
using namespace std;
const int N=1e6+5;
int n,a,dep[N],f[N][20],d[N],ans;
vector<int>e[N];
void read(){
    for(int i=1;i<n;i++){
        int u,v;
        scanf("%d%d",&u,&v);
        e[u].push_back(v);
        e[v].push_back(u);
    }
}
void dfs(int u,int fa){
    dep[u]=dep[fa]+1;//更新深度，方便lca
    f[u][0]=fa;//u的父节点是fa（确认父子关系）
    for(int i=1;i<20;i++)
        f[u][i]=f[f[u][i-1]][i-1];
    for(auto v:e[u])
        if(v!=fa)dfs(v,u);
}
int lca(int x,int y){
    if(dep[y]>dep[x])swap(x,y);//调整深度
    int t=dep[x]-dep[y],cnt=0;
    while(t){
        if(t%2)x=f[x][cnt];
        cnt++;
        t/=2;
    }
    if(x==y)return x;
    int maxstep=19;
    for(int i=maxstep;i>=0;i--)//循环找到lca的儿子
        if(f[x][i]!=f[y][i])x=f[x][i],y=f[y][i];
    x=f[x][0];
    y=f[y][0];
    return x;
}
void sum(int x){
    for(auto i:e[x]){
        if(f[i][0]==x){
            sum(i);
            d[x]+=d[i];
            if(ans<d[x])ans=d[x];
        }
    }
}
void solve(){
    for(int i=1;i<=a;i++){
        int x,y;
        scanf("%d%d",&x,&y);
        d[x]++,d[y]++;//差分让子节点++
        int t=lca(x,y);
        d[t]--;//LCA--
        if(f[t][0])d[f[t][0]]--;//LCA的父节点--（孤儿除外）
    }
    sum(1);
    cout<<ans;
}
int main(){
    scanf("%d%d",&n,&a);
    read();
    dfs(1,0);
    solve();
    return 0;
}