HDU 4714 Treecycle（树形dp）

http://acm.hdu.edu.cn/showproblem.php?pid=4714

题意：
给出一棵树，删除一条边和添加一条边的代价都是1，现在要把这棵树变成环，求需要花的最小代价。

思路：

其实就是要先把边变成树链，然后再把这些树链连接起来。

假如现在删除了n条边，那么就会形成n+1条树链，把这些树链连接成环则需要n+1代价，所以总的代价就是2n+1。

问题是什么求n呢？

如果以i为根的子树的子树大于等于2，那么它只能留下两条边，此时先把父亲节点的那条边删了，然后如果还多的话就删子树的边。这样一来，就形成了树链。

下面图解一下：

 1 #include<iostream>
 2 #include<algorithm>
 3 #include<cstring>
 4 #include<cstdio>
 5 #include<sstream>
 6 #include<vector>
 7 #include<stack>
 8 #include<queue>
 9 #include<cmath>
10 #include<map>
11 #include<set>
12 using namespace std;
13 typedef long long ll;
14 typedef pair<int,int> pll;
15 const int INF = 0x3f3f3f3f;
16 const int maxn = 1000000 + 5;
17 
18 int n;
19 int ans;
20 int sz[maxn];
21 vector<int> G[maxn];
22 
23 int dfs(int u, int fa)
24 {
25     int cnt=0;
26     for(int i=0;i<G[u].size();i++)
27     {
28         int v=G[u][i];
29         if(v==fa)  continue;
30         cnt+=dfs(v,u);
31     }
32     if(cnt>=2)
33     {
34         if(u==1)  ans+=cnt-2;
35         else ans+=cnt-1;
36         return 0;  //如果>=2就会删除父亲结点的边，那么父亲结点就不再需要计算这一棵子树了
37     }
38     return 1;
39 }
40 
41 int main()
42 {
43     //freopen("in.txt","r",stdin);
44     int T;
45     scanf("%d",&T);
46     while(T--)
47     {
48         scanf("%d",&n);
49         for(int i=1;i<=n;i++)  G[i].clear();
50 
51         for(int i=1;i<n;i++)
52         {
53             int u,v;
54             scanf("%d%d",&u,&v);
55             G[u].push_back(v);
56             G[v].push_back(u);
57         }
58         ans=0;
59         memset(sz,0,sizeof(sz));
60         dfs(1,-1);
61         printf("%d
",2*ans+1);
62     }
63     return 0;
64 }