题目地址：洛谷：【P3128】[USACO15DEC]最大流Max Flow – 洛谷

题目描述

FJ给他的牛棚的N(2≤N≤50,000)个隔间之间安装了N-1根管道，隔间编号从1到N。所有隔间都被管道连通了。
FJ有K(1≤K≤100,000)条运输牛奶的路线，第i条路线从隔间si运输到隔间ti。一条运输路线会给它的两个端点处的隔间以及中间途径的所有隔间带来一个单位的运输压力，你需要计算压力最大的隔间的压力是多少。

输入输出格式

输入格式：
The first line of the input contains N and K .
The next N−1 lines each contain two integers x and y (x≠y) describing a pipe between stalls x and y .
The next K lines each contain two integers s and t describing the endpoint stalls of a path through which milk is being pumped.

输出格式：
An integer specifying the maximum amount of milk pumped through any stall in the barn.

输入输出样例

输入样例#1：

5 10
3 4
1 5
4 2
5 4
5 4
5 4
3 5
4 3
4 3
1 3
3 5
5 4
1 5
3 4

输出样例#1：

9

题解

路径加考虑做成树上差分，倍增LCA处理LCA问题。最后把差分加起来得到真实值，统计最大值即可。

代码

// Code by KSkun, 2018/4
#include <cstdio>
#include <cstring>
#include <cmath> 

#include <algorithm>

typedef long long LL;

inline char fgc() {
    static char buf[100000], *p1 = buf, *p2 = buf;
    return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 100000, stdin), p1 == p2) ? EOF : *p1++;
}

inline int readint() {
    register int res = 0, neg = 1;
    register char c = fgc();
    while(c < '0' || c > '9') {
        if(c == '-') neg = -1;
        c = fgc();
    }
    while(c >= '0' && c <= '9') {
        res = res * 10 + c - '0';
        c = fgc();
    }
    return res * neg;
}

const int MAXN = 50005, INF = 1e9;

int n, k;

struct Edge {
    int to, nxt;
} gra[MAXN << 1];
int head[MAXN], tot;

inline void addedge(int u, int v) {
    gra[tot] = Edge {v, head[u]}; head[u] = tot++;
}

int lgn, anc[MAXN][20], dep[MAXN];

inline void dfs(int u) {
    for(int i = head[u]; ~i; i = gra[i].nxt) {
        int v = gra[i].to;
        if(v == anc[u][0]) continue;
        anc[v][0] = u;
        dep[v] = dep[u] + 1;
        dfs(v);
    }
}

inline void calanc() {
    for(int j = 1; (1 << j) <= n; j++) {
        for(int i = 1; i <= n; i++) {
            anc[i][j] = anc[anc[i][j - 1]][j - 1];
        }
    }
}

inline int querylca(int u, int v) {
    if(dep[u] > dep[v]) std::swap(u, v);
    int del = dep[v] - dep[u];
    for(int i = 0; (1 << i) <= del; i++) {
        if((1 << i) & del) v = anc[v][i];
    }
    if(u == v) return u;
    for(int i = lgn; i >= 0; i--) {
        if(anc[u][i] != anc[v][i]) {
            u = anc[u][i];
            v = anc[v][i];
        }
    }
    return anc[u][0];
}

int x, y, sum[MAXN], ans;

inline void dfs2(int u) {
    for(int i = head[u]; ~i; i = gra[i].nxt) {
        int v = gra[i].to;
        if(v == anc[u][0]) continue;
        dfs2(v);
        sum[u] += sum[v];
    }
    ans = std::max(ans, sum[u]);
}

int main() {
    memset(head, -1, sizeof(head));
    n = readint(); k = readint();
    lgn = log(n) / log(2);
    for(int i = 1; i < n; i++) {
        x = readint(); y = readint();
        addedge(x, y); addedge(y, x);
    }
    dfs(1);
    calanc();
    while(k--) {
        x = readint(); y = readint(); int lca = querylca(x, y);
        sum[x]++; sum[y]++; sum[lca]--; sum[anc[lca][0]]--;
    }
    dfs2(1);
    printf("%d", ans);
    return 0;
}