树上差分板子的板子

Miku

      #include<iostream>
#include<cstdio>
using namespace std;
int head[2*500001];
int p;
struct b{
    int to;
    int ne;
} e[2*500001];
int fa[2*500001][30];
int dep[2*500001];
int n,m,s;
int logg[2*500001]; 
int cha[500005];
int ans[500005];
int x,y;
void dfs(int now,int fat){
    dep[now]=dep[fat]+1;
    fa[now][0]=fat;
    for(int i=1;(1<<i)<=dep[now];++i){
        fa[now][i]=fa[fa[now][i-1]][i-1];
    }
    for(int i=head[now];i;i=e[i].ne){
        if(e[i].to!=fat)
        dfs(e[i].to,now);
    }
}
int lca(int x,int y){
    if(dep[x]<dep[y]){
        swap(x,y);
    }
    while(dep[x]>dep[y])
    x=fa[x][logg[dep[x]-dep[y]]-1];
    if(x==y)
    return x;
    for(int k=logg[dep[x]]-1;k>=0;k--){
        if(fa[x][k]!=fa[y][k]){
            x=fa[x][k];
            y=fa[y][k];
        }
    }
    return fa[x][0];
}
void print(int x,int fa){
//  cout<<x<<endl;
    for(int i=head[x];i;i=e[i].ne){
//          cout<<e[i].to;
        if(e[i].to!=fa){
            print(e[i].to,x);
            ans[x]+=ans[e[i].to];
        }
    }
    ans[x]+=cha[x];
    return ;
}
void add(int f,int t){
    p++;
    e[p].to=t;
    e[p].ne=head[f];
    head[f]=p;
}
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n-1;++i){
        scanf("%d%d",&x,&y);
        add(x,y);
        add(y,x);
    }
    dfs(1,0);
    for(int i=1;i<=n;++i)
        logg[i]=logg[i-1]+(1<<logg[i-1]==i);
    for(int i=1;i<=m;++i){
        scanf("%d%d",&x,&y);
        int o=lca(x,y);
        cha[x]++;
        cha[y]++;
        cha[o]--;
        cha[fa[o][0]]--;
    }
    print(1,0);
    x=0;
    for(int i=1;i<=n;++i){
        x=max(x,ans[i]);
    }
    cout<<x;
    return 0;
}