【Luogu P3128】[USACO15DEC] 最大流 Max Flow

Luogu P3128 [USACO15DEC] Max Flow

题目描述

Farmer John has installed a new system of $N-1$ pipes to transport milk between the $N$ stalls in his barn ($2 \leq N \leq 50,000$), conveniently numbered $1 \ldots N$. Each pipe connects a pair of stalls, and all stalls are connected to each-other via paths of pipes.

FJ is pumping milk between $K$ pairs of stalls ($1 \leq K \leq 100,000$). For the $i$th such pair, you are told two stalls $s_i$ and $t_i$, endpoints of a path along which milk is being pumped at a unit rate. FJ is concerned that some stalls might end up overwhelmed with all the milk being pumped through them, since a stall can serve as a waypoint along many of the $K$ paths along which milk is being pumped. Please help him determine the maximum amount of milk being pumped through any stall. If milk is being pumped along a path from $s_i*$ to $t_i$, then it counts as being pumped through the endpoint stalls $s_i$ and $t_i$, as well as through every stall along the path between them.

FJ给他的牛棚的 $N$ ($2 \leq N \leq 50,000$)个隔间之间安装了 $N-1$ 根管道，隔间编号从 $1$ 到$N$。所有隔间都被管道连通了。

FJ有 $K$ ($1 \leq N \leq 100,000$)条运输牛奶的路线，第 $i$ 条路线从隔间 $s_i$ 运输到隔间 $t_i$。一条运输路线会给它的两个端点处的隔间以及中间途径的所有隔间带来一个单位的运输压力，你需要计算压力最大的隔间的压力是多少。

输入格式

The first line of the input contains $N$ and $K$.

The next $N-1$ lines each contain two integers $x$ and $y$ ($x \ne y$) describing a pipe between stalls $x$ and $y$.

The next $K$ lines each contain two integers ss and tt 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 thebarn.

输入样例

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

输出样例

9

AC Code

#include<cstdio>
#include<vector>
#include<iostream>
using namespace std;
const int MAXN = 1e5 + 5;

vector<int> grp[MAXN];
int n, k, ans;
int dep[MAXN], f[MAXN][22], power[MAXN];

int lca(int x, int y) {
    if (dep[x] > dep[y]) swap(x, y);
    for (int i = 20; i >= 0; --i) {
        if (dep[x] <= dep[y] - (1 << i)) y = f[y][i];
    }
        if (x == y) return x;
        for (int i = 20; i >= 0; --i) {
            if (f[x][i] != f[y][i])
                x = f[x][i], y = f[y][i];
    }
    return f[x][0];
}

void inisharu(int pos, int fa) {
    dep[pos] = dep[fa] + 1;
    f[pos][0] = fa;
    for(int i = 0; f[pos][i]; ++i) f[pos][i + 1] = f[f[pos][i]][i];
    for(int i = 0; i < grp[pos].size(); ++i) {
        if(grp[pos][i] == fa) continue;
        inisharu(grp[pos][i], pos);
    }
}

void getans(int pos, int fa) {
    for(int i = 0;i < grp[pos].size(); ++i) {
        if(grp[pos][i] == fa) continue;
        getans(grp[pos][i], pos);
        power[pos] += power[grp[pos][i]];
    }
    ans = max(ans, power[pos]);
}
int main() {
    scanf("%d %d", &n, &k);
    for(int i = 0; i < n - 1; ++i) {
        int arg1, arg2;
        scanf("%d %d", &arg1, &arg2);
        grp[arg1].push_back(arg2);
        grp[arg2].push_back(arg1);
    }
    inisharu(1, 0);
    for(int i = 0; i < k; ++i) {
        int arg1, arg2;
        scanf("%d %d", &arg1, &arg2);
        int lca1 = lca(arg1, arg2);
        ++power[arg1];
        ++power[arg2];
        --power[lca1];
        --power[f[lca1][0]];
    }
    getans(1, 0);
    printf("%d", ans);
    return 0;
}