题目大意:给你一颗生成树,求你将它改造为一个环,即每个节点的度为二,对于每一个节点来说,可以删除或增加边,每次操作的消耗均为1,求将它改造成环的最小消耗.
Input:
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.
in:
1
4
1 2
2 3
2 4
out:
3
思路:对于某一点的度n,如果它的度超过了2,为了给他归并到环中就需要n-2次断开操作与n-2次重连,如果是根节点的话总共只需要2*(n-1)次操作.归并过程递归实现
#include <iostream> #include <cstring> #define N 1000005 using namespace std; int n,m,ans,cnt; bool vis[N]; int head[N]; struct Node { int to,next; } e[N<<1]; void add(int x,int y) { e[++cnt].to=y; e[cnt].next=head[x]; head[x]=cnt; } int dfs(int u) { int v,sum=0; for(int i=head[u]; i; i=e[i].next) { v=e[i].to; if(!vis[v]) { vis[v]=1; sum+=dfs(v); } } if(sum>=2) { if(u==1) ans=ans+2*(sum-2); else ans=ans+2*(sum-1); return 0; } return 1; } int main() { cin>>n; while(n--) { cin>>m; cnt=0; for(int i=1; i<m; i++) { int x,y; cin>>x>>y; add(x,y); add(y,x);//无向图 } ans=0; vis[1]=1; dfs(1); cout<<ans+1<<endl; memset(head,0,sizeof(head)); memset(vis,0,sizeof(vis)); } return 0; }