洛谷 P3128 [USACO15DEC]最大流Max Flow(LCA+树上差分)

Description:

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 \dots 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≤N≤50,000)个隔间之间安装了N-1根管道，隔间编号从1到N。所有隔间都被管道连通了。

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

Input:

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

The next $N - 1$ lines each contain two integers $x$ and $y$ ( $x \neq 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.

Output:

An integer specifying the maximum amount of milk pumped through any stall in the barn.

Sample Input:

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

Sample Output:

题目链接

求被经过次数最多的点。

思路很显然LCA+树上差分。

AC代码:

#include <bits/stdc++.h>
using namespace std;

const int maxn = 5e4 + 5;

struct Edge {
    int V, Next;
};

Edge edges[maxn << 1];
int Head[maxn];
int Tot;

void Init() {
    Tot = 0;
    memset(Head, -1, sizeof(Head));
}

void AddEdge(int U, int V) {
    edges[Tot] = Edge {V, Head[U]};
    Head[U] = Tot++;
}

int Rmq[maxn << 1];

struct ST {
    int Dp[maxn << 1][20];
    void Init(int N) {
        for (int i = 1; i <= N; ++i) {
            Dp[i][0] = i;
        }
        for (int j = 1; (1 << j) <= N; ++j) {
            for (int i = 1; i + (1 << j) - 1 <= N; ++i) {
                Dp[i][j] = Rmq[Dp[i][j - 1]] < Rmq[Dp[i + (1 << (j - 1))][j - 1]] ? Dp[i][j - 1] : Dp[i + (1 << (j - 1))][j - 1];
            }
        }
    }
    int Query(int A, int B) {
        if (A > B) {
            swap(A, B);
        }
        int Len = int(log2(B - A + 1));
        return Rmq[Dp[A][Len]] <= Rmq[Dp[B - (1 << Len) + 1][Len]] ? Dp[A][Len] : Dp[B - (1 << Len) + 1][Len];
    }
};

int Vertex[maxn << 1];
int First[maxn];
int Parent[maxn];
int LCATot;
ST St;

void LCADfs(int Cur, int Pre, int Depth) {
    Vertex[++LCATot] = Cur;
    First[Cur] = LCATot;
    Rmq[LCATot] = Depth;
    Parent[Cur] = Pre;
    for (int i = Head[Cur]; ~i; i = edges[i].Next) {
        if (edges[i].V == Pre) {
            continue;
        }
        LCADfs(edges[i].V, Cur, Depth + 1);
        Vertex[++LCATot] = Cur;
        Rmq[LCATot] = Depth;
    }
}

void LCAInit(int Root, int NodeNum) {
    LCATot = 0;
    LCADfs(Root, 0, 0);
    St.Init(2 * NodeNum - 1);
}

int QueryLCA(int U, int V) {
    return Vertex[St.Query(First[U], First[V])];
}

int N, K;
int Ans;
int Cnt[maxn];

int Dfs(int Cur, int Pre) {
    for (int i = Head[Cur]; ~i; i = edges[i].Next) {
        if (edges[i].V == Pre) {
            continue;
        }
        Cnt[Cur] += Dfs(edges[i].V, Cur);
    }
    Ans = max(Ans, Cnt[Cur]);
    return Cnt[Cur];
}

int main(int argc, char *argv[]) {
    Init();
    scanf("%d%d", &N, &K);
    for (int i = 1, X, Y; i < N; ++i) {
        scanf("%d%d", &X, &Y);
        AddEdge(X, Y);
        AddEdge(Y, X);
    }
    memset(Parent, 0, sizeof(Parent));
    LCAInit(1, N);
    memset(Cnt, 0, sizeof(Cnt));
    for (int i = 1, S, T; i <= K; ++i) {
        scanf("%d%d", &S, &T);
        int LCA = QueryLCA(S, T);
        Cnt[S]++; Cnt[T]++;
        Cnt[LCA]--; Cnt[Parent[LCA]]--;
    }
    Ans = 0;
    Dfs(1, 0);
    printf("%d\n", Ans);
    return 0;
}