Tree2cycle
Time Limit: 15000/8000 MS (Java/Others) Memory Limit: 102400/102400 K (Java/Others)
Total Submission(s): 4405 Accepted Submission(s): 1055
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.
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
Sample Output
3
题意：T组测试样例，每组样例中，有N个节点，(N-1)条双向边，问最少用多少花费(连接或断开费用都为1)使之成为环。环应满足三个条件：①N个节点和N条边 ②每个节点的度为2 ③每一个节点都能到达其他任何一个节点。
题解：树形DP。假设需要k次断开，可以将整个树拆成(k+1)条链，然后将这些链进行合并，需要(k+1)次。连接或断开费用都为1，所以一共需花费(2k+1)。
若使(2k+1)最小，则需让k最小。
如图，显然第二种方法最优。所以每次断开时，根节点断开[孩子个数-2(最多连两个孩子)]次，非根节点断开[孩子个数-2(最多留两个孩子和非根节点组成链)+1(断开非根节点和父节点)]。
提示：用vector存邻接矩阵，用G++提交会MLE，改用C++或用链式向前星即可。
代码：
#include<iostream>
#include<vector>
using namespace std;
const int maxn=1000005;
vector<int> e[maxn];
int ans;
int dfs(int p,int fa);
int main()
{
int T,n,i,a,b;
scanf("%d",&T);
while(T--)
{
for(i=0;i<maxn;i++) e[i].clear();
ans=0;
scanf("%d",&n);
for(i=1;i<n;i++)
{
scanf("%d%d",&a,&b);
e[a].push_back(b);
e[b].push_back(a);
}
dfs(1,-1);
printf("%d
",2*ans+1);
}
system("pause");
return 0;
}
int dfs(int p,int fa)
{
int i,v,sum=0;
for(i=0;i<e[p].size();i++)
{
v=e[p][i];
if(v==fa) continue;
sum+=dfs(v,p);
}
if(sum>=2)
{
if(p==1) ans+=sum-2;
else ans+=(sum-1);
return 0;
}
return 1;
}