Tree2cycle
Time Limit: 15000/8000 MS (Java/Others) Memory Limit: 102400/102400 K (Java/Others)
Total Submission(s): 1730 Accepted Submission(s): 401
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
Hint
In the sample above, you can disconnect (2,4) and then connect (1, 4) and
(3, 4), and the total cost is 3.
Source 2013 ACM/ICPC Asia Regional Online —— Warmup
Recommend liuyiding | We have carefully selected several similar problems for you: 5368 5367 5366 5365 5364 具体思路http://blog.csdn.net/dongdongzhang_/article/details/11395305 额，，不能算dp吧，充其量算个树上的乱搞。。会爆栈。。开栈就过了 ac代码
#include
#include
#pragma comment(linker, /STACK:102400000,102400000) int head[1000010],vis[1000010],cnt,ans; struct s { int u,v,next; }edge[1000010<<1]; void add(int u,int v) { edge[cnt].u=u; edge[cnt].v=v; edge[cnt].next=head[u]; head[u]=cnt++; } int dfs(int u) { vis[u]=1; int sum=0; for(int i=head[u];i!=-1;i=edge[i].next) { int v=edge[i].v; if(!vis[v]) { sum+=dfs(v); } } if(sum>=2) { if(u==1) ans+=(sum-2)*2; else ans+=(sum-1)*2; return 0; } return 1; } int main() { int t; scanf(%d,&t); while(t--) { int n; cnt=0; ans=0; memset(head,-1,sizeof(head)); memset(vis,0,sizeof(vis)); scanf(%d,&n); int i; for(i=1;i
?