2 shunfurh shunfurh 于 2017.11.15 00:16 提问

Tree2cycle

Problem 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

Csdn user default icon
上传中...
上传图片
插入图片
准确详细的回答,更有利于被提问者采纳,从而获得C币。复制、灌水、广告等回答会被删除,是时候展现真正的技术了!
其他相关推荐
hdu4714 Tree2cycle
下午心血来潮找来cjx第一次两人训练一套难度很低题目,就差这道思路正确不敢写,现在补一下。 题意:给你一棵树,每次删除一条边和增加一条边费用都是1,问最少的花费把一棵树变成 一条环。 思路:随手画了几个样例,发现不存在最少花费的策略,结果是唯一的。只要dfs序一遍判断每个点度数,大于2就说明需要删除这个点。思路很简单,清晰。 直接交MLE,需要扩栈,C++提交。#pragma commen
hdu4714 Tree2cycle
原题链接:     hdu 4714 Tree2cycle 题目大意:给一棵树节点数最多为1000000 ,把这棵树通过删边 和加边使这棵树变成一个环,其中删边和加边的的代价都为 1,输出最小代价。 题目分析:由于最终要形成一个环其拥有的的边一定为n,故可以只讨论要删除多少条边, 由于要形成环,删边后每个节点最多只能有两个节点,  如果 当前节点有多于2个子节点与其相连,其与父
hdu4714 Tree2cycle 树形DP
题目是问把一棵树通过剪边、加边形成一个环的最小代价。 分成两步,先把树剪成一些链,再把链连接成一个环。 My Code: //dp[u][0]表示u节点是所在链的端点时,以u节点为根节点的子树形成的最少的切边数。 //dp[u][1]表示u节点是所在链的中间的点时,以u节点为根节点的子树形成的最少的切边数。 #pragma comment(linker,"/STACK:102400000,1
hdu 4714 Tree2cycle dp
用树形dp做的,dp[t][i]表示t及其孩子入度都已经小于等于2并且t这个节点的入度等于i的最优解。 那么转移什么的自己想想就能明白了。 关键在于这个题目会暴栈,所以我用了一次bfs搜索出节点的顺序,然后再计算。 #include #include #include using namespace std; const int maxn=1e6+9; struct { int
hdu4714 Tree2cycle 树上乱搞
给一棵树,每次操作可以删一条边或者加一条边,
hdu4714 Tree2cycle(树形dp)
hdu4714题目给你一棵树,删去或者添加一条边花费的代价都是1,问最小的花费是多少使得经过删边加边后树变成一个环。思路还是云里雾里的,只知道最终每个节点的度数是2,那么当它的分支大于等于2的时候一定要删边,有删边就一定有对应的增边,对于根节点,我们要保留两个度,所以是son-2(son是子节点个数),其他的在保留2的同时要把对父的删去,是son-2+1,最后除了son*2之外,还要加一条边,所以加
HDU 4714 Tree2cycle
Tree2cycle Time Limit: 15000/8000 MS (Java/Others)    Memory Limit: 102400/102400 K (Java/Others) Total Submission(s): 382    Accepted Submission(s): 74 Problem Description A tree with N n
HDU 4714 Tree2Cycle
简单的DFS  有些大神有树形DP做的,效率要高很多。   若degree[i] > 2 ,则断开 i 与其父节点之间的边 和 degree[i] - 3 个子节点之间的边,其父节点 度 减一。   此时总消费增加  sum += (degree[i] - 2)*2;     1 #include 2 #include 3 #include 4 #include
Tree2cycle hdu4714 贪心
Description给定一棵N个节点的树,去掉这棵树的一条边需要消耗值1,为这个图的两个点加上一条边也需要消耗值1。树的节点编号从1开始。在这个问题中,你需要使用最小的消耗值(加边和删边操作)将这棵树转化为环,不允许有重边。 环的定义如下: (1)该图有N个点,N条边。 (2)每个顶点的度数为2。 (3)任意两点是可达的。 树的定义如下: (1)该图有N个点,N-1条边。
hdu 4714 Tree2cycle
乱搞题,要求用最少的操作把一颗树转化成一个环。其实就是把树分成最少的链,然后连接起来即可,仔细观察树的话会发现,一般一个点的度如果大于1的话,该点必然要断开一些连接,因为最终每个点的度都是2, 然后就是看点上断开那些连接了,其实,如果一个节点的除去父亲节点如果度大于1的话,断开与父亲节点的那条边必然是一种正解。。。于是问题就解决了,只需一遍dfs即可。在杭电交注意加上挂。。。不然会爆栈。。。 #