前言

前置芝士：树上差分

最开始读题堵了好久哈~

[洛谷 - 题目传送门]

题目大意

给出一棵树，和 K组 u,v，每组 u,v会在两点之间最短路径上每个点的权值 +1，求最大的点的权值

思路

因为是树，所以最短路径就是 u -> LCA -> v，只需要每个点都 +1 即可，可以使用树上差分优化，很容易 AC。

代码

// Problem: luogu - P3128 [USACO15DEC] Max Flow P
// by 1000ttank
#include <bits/stdc++.h>
using namespace std;
#define int long long 

#define endl '\n'

const int maxn=5e5+10; // 点的最大数
const int maxlog=30; // 2^30 肯定大于点的个数，没有问题
vector<int> g[maxn]; // 题目给出
int root=1;
int d[maxn];
int lg[maxn];
int dep[maxn];
int fa[maxn][maxlog];
void dfs(int u,int _fa) {
    fa[u][0]=_fa;
    dep[u]=dep[_fa]+1;
    for (auto v:g[u]) {
        if (v==_fa) continue;
        dfs(v,u);
    }
}
void init(int n) {
    dfs(root,0);
    for (int j=1;j<maxlog;j++) {
        for (int i=1;i<=n;i++) {
            fa[i][j]=fa[fa[i][j-1]][j-1];
        }
    }
}
int LCA(int u,int v) {
    if (dep[u]>dep[v]) swap(u,v);
    for (int i=maxlog-1;i>=0;i--) { // 跳到同一层
        if (dep[u]<=dep[fa[v][i]]) v=fa[v][i];
    } 
    if (u==v) return u; // 特判
    for (int i=maxlog-1;i>=0;i--) { // 找最近公共祖先
        if (fa[u][i]!=fa[v][i]) u=fa[u][i],v=fa[v][i];
    }
    return fa[u][0];
}
void dfs2(int u,int _fa) {
    for (auto v:g[u]) {
        if (v==_fa) continue;
        dfs2(v,u);
        d[u]+=d[v];
    }
}
void solve() {
    int n,m; cin >> n >> m;
    for (int i=1;i<n;i++) {
        int u,v; cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    init(n);
    for (int i=1;i<=m;i++) {
        int u,v; cin >> u >> v;
        int l=LCA(u,v);
        d[u]++,d[v]++,d[l]--,d[fa[l][0]]--;
    }
    dfs2(root,0);
    int ans=0;
    for (int i=1;i<=n;i++) {
        ans=max(ans,d[i]);
    }
    cout << ans << endl;
}
signed main() {
    #define USACO

    #ifdef USACO
    #ifndef LOCAL
    freopen("maxflow.in","r",stdin);
    freopen("maxflow.out","w",stdout);
    #endif
    #endif

    ios::sync_with_stdio(false); cin.tie(nullptr);
    int T=1;
    // cin >> T;
    while (T--) {
        solve();
    }
    return 0;
}