题目链接:https://www.luogu.com.cn/problem/P3128
题目大意:


思路:树上差分模板题。讲解的博客:
https://blog.csdn.net/a_forever_dream/article/details/83505521

对点a-b的点:
对于树上的区间修改问题,也就是a[x]~ a[y]+1,我们只需要将d[x]+1,d[y]+1,d[lca(x,y)]−1,d[fa[lca(x,y)]]−1即可!

对点a-b的边:
对于树上的区间修改问题,也就是a[x]~ a[y]+1,我们只需要将d[x]+1,d[y]+1,d[lca(x,y)]−2即可!

ps:不知道为什么多开10倍空间才能过。

#include <bits/stdc++.h>
#define LL long long
using namespace std;
const int maxn=500005;

int f[maxn][21];    //保存i节点的2^j祖先
int d[maxn], n, k;  //保存每个节点的深度
int c[maxn];        //差分数组
int ans=0;
vector<int> e[maxn];

void dfs(int u)
{
    for(int i=0;i<e[u].size();i++){
        int v=e[u][i];
        if(v!=f[u][0]){  //无向边,不能返回父亲节点
            d[v]=d[u]+1;//树的深度
            f[v][0]=u;
            dfs(v);
        }
    }
}

void init()
{
    for(int j=1;(1<<j)<=n;j++){
        for(int i=1;i<=n;i++){
            f[i][j]=f[f[i][j-1]][j-1];
        }
    }
}

int lca(int a, int b)
{
    if(d[a]>d[b]){      //让b的深度更深
        swap(a, b);
    }
    int p=d[b]-d[a];   //深度差
    for(int i=0;(1<<i)<=p;i++){//让a, b的深度相同
        if((1<<i)&p){
            b=f[b][i];
        }
    }
    if(a==b){        //a或b是LCA
        return b;
    }

    for(int i=(int)log(maxn);i>=0;i--){//a, b一起找LCA
        if(f[a][i]!=f[b][i]){
            a=f[a][i];b=f[b][i];
        }
    }
    b=f[a][0];

    return b;
}

int dfs_max(int u)
{
    int s=c[u];
    for(int i=0;i<e[u].size();i++){
        int v=e[u][i];
        if(v!=f[u][0]){  //无向边,不能返回父亲节点
            s+=dfs_max(v);
        }
    }
    ans=max(ans, s);

    return s;
}

int main(){

    int k, a, b;
    scanf("%d%d", &n, &k);
    for(int i=1; i<n; i++){
        scanf("%d%d", &a, &b);
        e[a].push_back(b);
        e[b].push_back(a);
    }
    dfs(1);
    init();
    for(int i=1; i<=k; i++){
        scanf("%d%d", &a, &b);
        c[a]++;c[b]++;
        int Lca=lca(a, b);
        c[Lca]--; c[f[Lca][0]]--;
    }
    dfs_max(1);
    printf("%d\n", ans);

    return 0;
}