P3128 [USACO15DEC]Max Flow P 树上点差分

//题意：给出一棵树，现在有一操作：给出两点，将两点之间的路径都加1，最后统计整棵树中值最大的点是谁
//思路：树上路径问题，树剖+线段树可以解决，但是因为只是简单的维护区间加减，用不着树剖那么
//      麻烦，所以我们直接上树上差分便好
#include<bits/stdc++.h>
using namespace std;
#define maxn 50010
#define ll long long
#define res register int
struct Node {
    int to, next;
};
Node edge[maxn << 2]; //链式前向星要多开几倍数组
int head[maxn << 2], power[maxn], n, m, d[maxn], fa[maxn][30], ans, num;

inline int read() { //快读
    int s = 0;
    char c = getchar();
    while (c < '0' || c>'9') c = getchar();
    while (c >= '0' && c <= '9') s = s * 10 + c - '0', c = getchar();
    return s;
}
//链式前向星
inline void add(int x, int y) { edge[++num].to = y, edge[num].next = head[x], head[x] = num; }
inline void work(int u, int fath) {
    d[u] = d[fath] + 1, fa[u][0] = fath;
    for (res i = 0; fa[u][i]; ++i) fa[u][i + 1] = fa[fa[u][i]][i];//边dfs边把倍增预处理了
    for (res i = head[u]; i; i = edge[i].next) {
        int e = edge[i].to;
        if (e != fath) work(e, u);
    }
}
//倍增求LCA
inline int Lca(int u, int v) {
    if (d[u] > d[v]) swap(u, v);
    for (res i = 20; i >= 0; --i) if (d[u] <= d[v] - (1 << i)) v = fa[v][i];
    if (u == v) return u;
    for (res i = 20; i >= 0; --i) if (fa[u][i] != fa[v][i]) u = fa[u][i], v = fa[v][i];
    return fa[u][0];
}
inline void Get(int u, int fath) {
    for (res i = head[u]; i; i = edge[i].next) {
        int e = edge[i].to;
        if (e == fath) continue;
        Get(e, u);
        power[u] += power[e];
    }
    ans = max(ans, power[u]);
}
int main() {
    n = read(), m = read();
    int x, y;
    for (res i = 1; i < n; ++i) {
        x = read(), y = read();
        add(x, y); add(y, x);
    }
    work(1, 0);//为求lca做准备
    for (res i = 1; i <= m; ++i) {
        x = read(), y = read();
        int lca = Lca(x, y);
        ++power[x]; ++power[y]; --power[lca]; --power[fa[lca][0]]; //树上差分
    }
    Get(1, 0);
    printf("%d\n", ans);
    return 0;
}