RiseOJ – 최대 유량

설명

농부 존은 헛간에 있는 $$N$$ 개의 축사( $2 \leq N \leq 50,000$ ) 사이에서 우유를 운반하기 위해 $$N-1$$ 개의 파이프로 이루어진 새 시스템을 설치했다. 축사에는 $1 \ldots N$ 의 번호가 붙어 있다. 각 파이프는 두 축사를 연결하며, 모든 축사는 파이프 경로를 통해 서로 연결되어 있다.

FJ는 $$K$$ 쌍의 축사( $1 \leq K \leq 100,000$ ) 사이에 우유를 펌프질하고 있다. $$i$$ 번째 쌍에 대해 두 축사 $$s_i$$ 와 $$t_i$$ 가 주어지는데, 이는 단위 속도로 우유가 펌프질되는 경로의 양 끝점이다. FJ는 어떤 축사가 그곳을 통과하는 우유로 넘쳐나지 않을까 걱정한다. 한 축사가 우유가 펌프질되는 $$K$$ 개의 경로 중 여러 경로의 경유지가 될 수 있기 때문이다. 임의의 축사를 통과하는 우유량의 최댓값을 구해 FJ를 도와주자. $$s_i$$ 에서 $$t_i$$ 로 가는 경로를 따라 우유가 펌프질된다면, 그 우유는 양 끝점 축사 $$s_i$$ 와 $$t_i$$ 뿐 아니라 두 축사 사이 경로 위의 모든 축사도 통과하는 것으로 센다.

Problem credits: Brian Dean

제약

Problem credits: Brian Dean

입력 형식

입력의 첫째 줄에 $$N$$ 과 $$K$$ 가 주어진다.

다음 $$N-1$$ 개의 줄에는 각각 축사 $$x$$ 와 $$y$$ 사이의 파이프를 나타내는 두 정수 $$x$$ 와 $$y$$ ( $x \ne y$ )가 주어진다.

다음 $$K$$ 개의 줄에는 각각 우유가 펌프질되는 경로의 양 끝 축사를 나타내는 두 정수 $$s$$ 와 $$t$$ 가 주어진다.

출력 형식

헛간의 임의의 축사를 통과하는 우유량의 최댓값을 하나의 정수로 출력한다.

Standard input / output

This problem is judged over standard input/output. The original contest used named files — if you prefer the classic interface, tick “File I/O” on the submit form and read/write these files instead:

입력을 읽을 파일 maxflow.in · 출력을 쓸 파일 maxflow.out

예제 1

입력

출력

문제 정보

riseoj 작성

출처 올림피아드 > USACO > 2015-2016 > December > Platinum

올림피아드 > USACO > 2015-2016 > December > Platinum

태그

JudgeUSACO

최대 유량

평가 및 의견

풀이 제출