编程介的小学生
2017-11-14 16:16Tree2cycle
10Problem Description
A tree with N nodes and N-1 edges is given. To connect or disconnect one edge, we need 1 unit of cost respectively. The nodes are labeled from 1 to N. Your job is to transform the tree to a cycle(without superfluous edges) using minimal cost.
A cycle of n nodes is defined as follows: (1)a graph with n nodes and n edges (2)the degree of every node is 2 (3) each node can reach every other node with these N edges.
Input
The first line contains the number of test cases T( T<=10 ). Following lines are the scenarios of each test case.
In the first line of each test case, there is a single integer N( 3<=N<=1000000 ) - the number of nodes in the tree. The following N-1 lines describe the N-1 edges of the tree. Each line has a pair of integer U, V ( 1<=U,V<=N ), describing a bidirectional edge (U, V).
Output
For each test case, please output one integer representing minimal cost to transform the tree to a cycle.
Sample Input
1
4
1 2
2 3
2 4
Sample Output
3
- 点赞
- 回答
- 收藏
- 复制链接分享
1条回答
为你推荐
- 在Go中实现堆栈以存储结构的正确方法是什么?
- stack
- types
- 1个回答
- jQuery .live多次触发!
- ajax
- php
- jquery
- 2个回答
- Yii NestedSetBehavior内存使用情况
- memory-management
- yii
- model
- php
- 2个回答
- 数据量太大,必须用scanf,在数据量大的时候,这个程序的算法怎么实现?
- r语言
- Golang
- erlang
- 1个回答
- 家系树软件中的循环
- c++
- assertions
- family-tree
- graph
- cycle
- 0个回答