# UVa 908

Jump to navigation
Jump to search

## Problem Number - Problem Name[edit]

## Summary[edit]

Given a set of N edges of a tree, output the total cost of this tree. Then given another set of K+M edges, construct an MST using these edges and output its cost.

## Gotchas[edit]

Just a naive MST constructing problem. Nothing special to consider

## Notes[edit]

- In the problem statement, N may be as large as 1,000,000, and 1<=M<= N*(N-1)/2, which is large than 2^32.

But the data sets is seem to be so weak that such an M does not exist, which means that using int is enough.

By the way, do not print a blank line after the last test case.

## Input[edit]

5 1 2 5 1 3 5 1 4 5 1 5 5 1 2 3 2 6 1 2 5 1 3 5 1 4 5 1 5 5 3 4 8 4 5 8 4 1 2 5 1 3 5 1 4 5 1 2 3 2 4 1 2 5 1 3 5 1 4 5 3 4 8

## Output[edit]

20 17 15 12