BuringStraw

BuringStraw

Luogu P3128 Max Flow

P3128 [USACO15DEC] Max Flow#

Problem Description#

FJ has installed N (2≤N≤50,000) pipes between the N-1 stalls in his cowshed, numbered from 1 to N. All stalls are connected by pipes.

FJ has K (1≤K≤100,000) milk transportation routes. The i-th route transports milk from stall si to stall ti. A transportation route will bring one unit of transportation pressure to the stalls at its two endpoints and all the stalls in between. You need to calculate the maximum pressure among all the stalls.

Input and Output#

Input:#

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.

Output:#

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

Input and Output Examples#

Input Example #1:

Output Example #1:

Solve#

Tree Difference template problem.

It's difficult, took me the whole afternoon

(How do I store the tree again?)

At first, I thought it would be difficult to find the parent using the forward star method. After struggling for a while, I still used the forward star method.

Then I forgot about LCA. I even used Tarjan to find the LCA between every two points, and the array was too small. As a result, it resulted in TLE+MLE.

TLE+MLE

I changed to using doubling to find the LCA, but it still didn't pass the test cases. Later, I found out that I was using the array storing the parent in the Tarjan LCA...

Then the reason why it only passed one or two points was actually:

When there was an error, I wrote two initialization methods, dfs and bfs, and now both can pass.

The complete code is as follows:

There is also a 41-point code (Tarjan)

Loading...
Ownership of this post data is guaranteed by blockchain and smart contracts to the creator alone.