레이팅 미적용농부 존은 자신의 농장이 잘 연결되어 있다는 것에 자부심을 가지고 있다. 농장은 \(N\)개의 목초지 (\(2 \leq N \leq 50,000\))로 이루어져 있으며, 이들 중 일부 쌍이 \(N-1\)개의 양방향 길로 연결되어 있고, 각 길의 길이는 1이다. 농부 존은 이 길들을 적절히 따라가면 어떤 목초지에서든 다른 어떤 목초지로도 이동할 수 있다는 것을 알았다.
농부 존의 농장은 연결되어 있지만, 그는 길 하나가 막히면 어떤 일이 일어날지 걱정하고 있다. 길 하나가 막히면 농장은 사실상 두 개의 분리된 목초지 집합으로 나뉘어, 소들은 각 집합 안에서는 이동할 수 있지만 집합 사이를 오갈 수는 없게 된다. 그래서 농부 존은 \(M\)개의 추가 양방향 길 (\(1 \leq M \leq 50,000\))을 건설한다. 각 추가 길의 길이는 \(10^9\) 이하의 양의 정수이다. 소들은 원래의 길 중 하나가 막히지 않는 한, 이동할 때 원래의 길만 사용한다.
원래의 길 중 하나가 막히면 농장은 두 개의 분리된 부분으로 나뉘고, 농부 존은 추가 길 중에서 이 두 부분의 연결을 복구하는 대체 길 하나를 선택하여, 소들이 다시 어떤 목초지에서든 다른 어떤 목초지로도 이동할 수 있게 한다.
농장의 원래 길 각각에 대해, 농부 존이 가장 짧은 적절한 대체 길을 선택할 수 있도록 도와주자.
출제자: Brian Dean
출제자: Brian Dean
입력의 첫째 줄에 \(N\)과 \(M\)이 주어진다. 다음 \(N-1\)개의 줄에는 각각 원래 길 하나를 나타내는 정수 \(p\), \(q\)가 주어진다. 여기서 \(p \neq q\)는 그 길이 연결하는 두 목초지이다 (\(1 \ldots N\) 범위). 나머지 \(M\)개의 줄에는 각각 추가 길 하나를 나타내는 세 정수 \(p\), \(q\), \(r\)가 주어지며, \(r\)는 그 길의 길이이다. 임의의 두 목초지 사이에는 길이 최대 하나만 존재한다.
입력에 나타난 순서대로 \(N-1\)개의 원래 길 각각에 대해, 그 길이 막혔을 때 농장을 다시 연결할 수 있는 가장 짧은 적절한 대체 길의 길이를 출력한다. 적절한 대체 길이 존재하지 않으면 -1을 출력한다.
disrupt.in · 출력을 쓸 파일 disrupt.out6 3
1 2
1 3
4 1
4 5
6 5
2 3 7
3 6 8
6 4 57
7
8
5
5riseoj 작성
출처 올림피아드 > USACO > 2017-2018 > US Open > Platinum