Max Flow P|P3128

https://www.luogu.com.cn/problem/P3128

裸的树上差分，不讲了。

//裸的树上差分吧
//「兴奋」
#include<iostream>
#include<cstring>
#define int long long
using namespace std;
//快读好习惯
inline int read(){
    int s=0,f=1;
    char c=getchar();
    while(c<48 || c>57){if(c=='-')f=-f;c=getchar();}
    while(c>=48 && c<=57)s=s*10+c-48,c=getchar();
    return s*f;
}
const int MAXN=5e4+10;
const int MAXM=1e5+10;
int n,m;
//无根树
int tree[MAXN];
//树上差分就难蚌
//LCA啊啊啊
//不急慢慢来
//艹忘定义树了。。。
int head[MAXN];
struct tree{
    int to;
    int next;
}edge[MAXN*2];//双向！！！！！！
int _cnt=0;
void add(int u,int v){
    edge[_cnt].to=v;
    edge[_cnt].next=head[u];
    head[u]=_cnt++;
}
int depth[MAXN];
int d[MAXN][20];//lca倍增用的
//定义1是根
void dfs(int x,int dep){
    depth[x]=dep;
    for(int i=head[x];i!=-1;i=edge[i].next){
        int nxt=edge[i].to;
        if(depth[nxt])continue;
        d[nxt][0]=x;
        for(int i=1;i<20;i++){
            d[nxt][i]=d[d[nxt][i-1]][i-1];
        }
        dfs(nxt,dep+1);
    }
    return;
}
//LCA
int LCA(int u,int v){
    if(depth[u]<depth[v]){//选最低的
        swap(u,v);
    }
    for(int i=19;i>=0;i--){//跳到一起
        if(depth[d[u][i]]>=depth[v])u=d[u][i];
    }
    if(u==v)return u;
    for(int i=19;i>=0;i--){
        if(d[u][i]!=d[v][i]){
            u=d[u][i];
            v=d[v][i];
        }
    }
    return d[u][0];
}
//递归求解答案
bool vis[MAXN];
int dfs2(int x){
    int ret=tree[x];
    vis[x]=1;
    for(int i=head[x];i!=-1;i=edge[i].next){
        int nxt=edge[i].to;
        if(vis[nxt])continue;
        ret+=dfs2(nxt);
    }
    return tree[x]=ret;
}
signed main(){
    memset(head,-1,sizeof(head));   
    n=read(),m=read();
    int u,v;
    for(int i=1;i<n;i++){
        u=read(),v=read();
        add(u,v);
        add(v,u);
    }
    dfs(1,1);//深度也是1
    for(int i=0;i<m;i++){
        //打个LCAQQQQQQQQQQQQQQQ
        u=read(),v=read();
        int lca=LCA(u,v);
        tree[u]++;
        tree[v]++;
        tree[lca]--;
        tree[d[lca][0]]--;
    }
    dfs2(1);
    int ans=0;
    for(int i=1;i<=n;i++){
        ans=max(ans,tree[i]);
    }
    cout<<ans;
    return 0;
}