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).
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
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
#include <stdio.h>
#include <string.h>
#pragma comment(linker, "/STACK:1024000000,1024000000")
#define Maxn 1010000 struct Edge
{
int v;
struct Edge *next;
}*head[Maxn<<],edge[Maxn<<]; int n,cnt,ans;
void add(int a,int b)
{
edge[++cnt].v=b,edge[cnt].next=head[a];
head[a]=&edge[cnt];
} int dfs(int cur,int pa) //返回分支个数
{
int res=;
struct Edge * p=head[cur]; while(p)
{
if(p->v!=pa) res+=dfs(p->v,cur);
p=p->next;
}
if(res>=) //超过两个分支，将其它分支链过来
{
if(cur==) ans+=res-; //树根不用链到其它地方
else ans+=res-; //选两个，其它的边都要断开和重新链接一次
return ; //断开了
}
else return ; //作为一个单支
} int main()
{
int t;
scanf("%d",&t);
while(t--)
{
scanf("%d",&n);
cnt=;
memset(head,NULL,sizeof(head));
for(int i=;i<n;i++)
{
int a,b;
scanf("%d%d",&a,&b);
add(a,b);
add(b,a);
}
ans=;
dfs(,);
printf("%d\n",ans*+);
}
return ;
}