#PU842. USACO 2018 US Open Contest, Platinum — Problem 3. Disruption

    ID: 1650 传统题 文件IO:disrupt 2000ms 256MiB 尝试: 0 已通过: 0 难度: 省选/NOI- 上传者: 标签>USACO赛事:open18来源:usaco.orgscoring:equal_test_cases最短路

USACO 2018 US Open Contest, Platinum — Problem 3. Disruption

USACO 2018 US Open Contest, Platinum — Problem 3. Disruption

题目描述

Farmer John prides himself on running a well-connected farm. The farm is a collection of NN pastures (2≤N≤50,0002 \leq N \leq 50,000), pairs of which are connected with N−1N-1 bi-directional pathways, each having unit length. Farmer John notices that using an appropriate series of these pathways, it is possible to travel from any pasture to any other pasture. Although FJ's farm is connected, he worries what might happen if one of the pathways gets blocked, as this would effectively partition his farm into two disjoint sets of pastures, where the cows could travel within each set but not between the sets. FJ therefore builds a set of MM additional bi-directional pathways (1≤M≤50,0001 \leq M \leq 50,000), each with a positive integer length at most 10910^9. The cows still only use the original pathways for transit, unless one of these becomes blocked. If one of the original pathways becomes blocked, the farm becomes partitioned into two disjoint pieces, and FJ will select from among his extra pathways a single replacement pathway that re-establishes connectivity between these two pieces, so the cows can once again travel from any pasture to any other pasture. For each of the original pathways on the farm, help FJ select the shortest suitable replacement pathway.

输入格式

The first line of input contains NN and MM. Each of the next N−1N-1 lines describes an original pathway using integers pp, qq, where p≠qp \neq q are the pastures connected by the pathway (in the range 1…N1 \ldots N). The remaining MM lines each describe an extra pathway in terms of three integers: pp, qq, and rr, where rr is the length of the pathway. At most one pathway runs between any pair of pastures.

输出格式

For each of the N−1N-1 original pathways in the order they appear in the input,

数据范围

(见题面原文)

样例

样例 1

6 3
1 2
1 3
4 1
4 5
6 5
2 3 7
3 6 8
6 4 5
7
7
8
5
5
Problem credits: Brian Dean