树形dp专辑

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

input

5//5个结点

1 1//表示结点2到结点1有一条权值为1的边

2 1//表示结点3到结点2有一条权值为1的边

3 1

1 1

要我们求从任意结点出发的最长路径。

思路：一棵树上从某个结点出发的最长路径，肯定是①从该结点出发经由子树到大叶子结点。②从该结点出发经由父结点，然后到大叶子结点。这两者中的最大者

　　①可以用一遍dfs求出任意结点到叶子结点的最大值。

　　②也是用一遍dfs求出任意结点经由父结点到达叶子结点的最大值

　　最后两者取max即可

 1 #include <stdio.h>
 2 #include <string.h>
 3 #include <stdlib.h>
 4 #include <algorithm>
 5 #include <iostream>
 6 #include <queue>
 7 #include <stack>
 8 #include <vector>
 9 #include <map>
10 #include <set>
11 #include <string>
12 #include <math.h>
13 using namespace std;
14 typedef long long LL;                   
15 const int INF = 1<<30;
16 const int N = 10000 + 10;
17 struct computer
18 {
19     int v,len;
20 };
21 vector<computer> g[N];
22 int maxn[N],smax[N];
23 int maxnId[N],smaxId[N];
24 int up[N];//up[]记录的是从父亲结点转到根结点的最大值
25 //dfs生成一棵树，然后求的每个结点到叶子结点的最大值和次大值， 最大值和次大值不在一个分支上面
26 void dfs1(int u, int fa)
27 {
28     maxn[u] = smax[u] = 0;
29     for(int i=0; i<g[u].size(); ++i)
30     {
31         int v = g[u][i].v;
32         if(v!=fa)//如果u的一个分支v用来更新最长路，那么就不会更新次长路，所以maxn[u]是u最长的一个分支，smax[v]是v次长的一个分支
33             //因为是树，所以分支是没有交点的。
34             //感觉求出来的次长路不是次长路
35         {
36             dfs1(v,u);
37             if(maxn[u] < maxn[v] + g[u][i].len)//最长
38             {
39                 smax[u] = maxn[u];
40                 maxn[u] = maxn[v] + g[u][i].len;
41                 smaxId[u] = maxnId[u];
42                 maxnId[u] = v;//结点u的最长路是经过结点v这个分支然后到达叶子结点
43             }
44             else if(smax[u] < maxn[v] + g[u][i].len)//次长
45             {
46                 smax[u] = maxn[v] + g[u][i].len;
47                 smaxId[u] = v;
48             }
49         }
50     }
51 }
52 
53 void dfs2(int u, int fa)
54 {
55     for(int i=0; i<g[u].size();++i)
56     {
57         int v = g[u][i].v;
58         if(v==fa) continue;
59         if(v!=maxnId[u])//如果父节点到根结点的最大值不是从v这个分支接入的，那么v从到结点再到根结点的最大值为
60         {
61             up[v] = max(up[u],maxn[u])+g[u][i].len;//v到父亲，然后父亲到叶子结点的最大值或者父亲经由父亲的父亲到达叶子结点的最大值
62         }
63         else//如果父节点到根结点的最大是从v这个分支接入的，那么fmax[u]+g[u][i].len就会有重叠的部分，所以只能用smax[u]+g[u][i].len
64         {
65             up[v] = max(up[u],smax[u]) + g[u][i].len;
66         }
67         dfs2(v,u);
68     }
69 }
70 int main()
71 {
72     int n,i,x,len;
73     computer tmp;
74     while(scanf("%d",&n)!=EOF)
75     {
76         
77         for(i=1; i<=n; ++i)
78             g[i].clear();
79         for(i=2; i<=n; ++i)
80         {
81             scanf("%d%d",&x,&len);
82             tmp.v = x;
83             tmp.len = len;
84             g[i].push_back(tmp);
85             tmp.v = i;
86             g[x].push_back(tmp);
87         }
88         dfs1(1,-1);//设1为根结点，然后dfs，生成dfs树
89         up[1] = 0;//更结点没有父亲结点，所以经由父亲结点到达根结点的最大值为0
90         dfs2(1,-1);
91         
92         for(i=1; i<=n; ++i)
93             printf("%d
",max(maxn[i],up[i]));
94     }
95     return 0;
96 }

View Code

删点删边类

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

给定n和m

然后给定n-1条边和权值

要求删除边使得所有的叶子结点与根结点不连通，删边的花费为边的权值

要求使得花费总和小于m，且所有删边花费中的最大值最小。

思路：dp[u]是使得所有的叶子结点与结点u不连通的最小花费， dp[u] += min(dp[v],edge(u,v).cost);

　　这样子只是求出了删除所有叶子结点的总的最小花费。

　　还有一个要求是最大值最小，最大值最小，一般都是用二分枚举最大值。

　　那么状态转移方程就改为了 if(edge(u,v).cost > mid) dp[u] += dp[v]; 如果边的权值大于我们枚举的最大值，那么这条边就是不可取的

　　　　　　　　　　　　　　　else dp[u] +=min(dp[v],edge(u,v).cost);

 1 //切断某些边，使得所有的叶子结点与根结点不联通，这些权值之和要小于m，且是的所有切断的边中的权值的最大值最小
 2 
 3 /*
 4 dp[i] += min(dp[son],edge(i->son))
 5 
 6 
 7 二分枚举边权值的最大值
 8 存在性问题都是用二分枚举
 9 */
10 #include <stdio.h>
11 #include <string.h>
12 #include <stdlib.h>
13 #include <algorithm>
14 #include <iostream>
15 #include <queue>
16 #include <stack>
17 #include <vector>
18 #include <map>
19 #include <set>
20 #include <string>
21 #include <math.h>
22 using namespace std;
23 typedef long long LL;                   
24 const int INF =  1000001;//这个不能太大，因为有可能所有的边都不可取，然后dp[u] += dp[v] ,那么dp[u]就加了很多的INF
25 const int N = 1000+10;
26 struct node
27 {
28     int v,cost;
29 };
30 vector<node> g[N];
31 int dp[N];
32 int mid;
33 int ans;
34 
35 void dfs(int u, int fa)
36 {
37     dp[u] = 0;
38     bool flag = false;
39     for(int i=0; i<g[u].size(); ++i)
40     {
41         int v = g[u][i].v;
42         if(v==fa) continue;
43         flag = true;
44         dfs(v,u);
45         // 如果边的权值大于我们枚举的最大值，那么这条边就是不可取的
46         if(g[u][i].cost > mid) dp[u] += dp[v];
47         else
48             dp[u] += min(dp[v],g[u][i].cost);
49         
50     }
51     if(!flag)
52         dp[u] = INF;
53 }
54 int main()
55 {
56     int n,m,i,a,b,c;
57     node tmp;
58     while(scanf("%d%d",&n,&m),n)
59     {
60         for(i=1; i<=n; ++i)
61             g[i].clear();
62         for(i=1; i<n; ++i)
63         {
64             scanf("%d%d%d",&a,&b,&c);
65             tmp.cost = c;
66             tmp.v = a;
67             g[b].push_back(tmp);
68             tmp.v = b;
69             g[a].push_back(tmp);
70         }
71         int low = 1,high = m;
72         ans = INF;
73         while(low<=high)
74         {
75             mid = (low + high) >> 1;
76             dfs(1,-1);
77             if(dp[1]<=m)//如果按照我们枚举的最大值仍然能使得总花费小于m，那么该最大值是可行的
78             {
79                 ans = mid;
80                 high = mid - 1;
81             }
82             else
83                 low = mid + 1;
84         }
85         if(ans == INF)
86             puts("-1");
87         else
88         printf("%d
",ans);
89     }
90     return 0;
91 }

View Code

poj3107

给定n和n-1条边。

问删除哪个点，使得剩下的联通分支，结点个数最大的最小。

num[u] 表示子树u有多少个结点,dp[u] 表示删除这个结点后，剩下的最大的联通分支的结点个数

从结点u出发的所有分支获得个数最多的联通分支

（树的重心即删除重心后，会使得最大的联通分支的结点个数最小）

if(v==fa)

dp[u] = max(dp[u],n-num[u]);//

else

dp[u] = max(dp[u],num[v]);

注意：这里用STL会超时。

 1 #include <stdio.h>
 2 #include <string.h>
 3 #include <stdlib.h>
 4 #include <algorithm>
 5 #include <iostream>
 6 #include <queue>
 7 #include <stack>
 8 #include <vector>
 9 #include <map>
10 #include <set>
11 #include <string>
12 #include <math.h>
13 using namespace std;
14 typedef long long LL;                   
15 const int INF = 1<<30;
16 const int N = 50000 + 10;
17 int num[N];
18 int dp[N];
19 int n;
20 int head[N],e;
21 struct node
22 {
23     int v,next;
24 }g[N*2];
25 void addEdge(int a, int b)
26 {
27     g[e].v = b;
28     g[e].next = head[a];
29     head[a] = e++;
30 }
31 void dfs1(int u, int fa)
32 {
33     num[u] = 1;
34     for(int i=head[u]; i!=-1; i=g[i].next)
35     {
36         int v = g[i].v;
37         if(v==fa)  continue;
38         dfs1(v,u);
39         num[u] += num[v];
40     }
41 }
42 void dfs2(int u, int fa)
43 {
44     dp[u] = 0;
45     for(int i=head[u]; i!=-1; i=g[i].next)
46     {
47         int v = g[i].v;
48         if(v==fa)
49         {
50             dp[u] = max(dp[u],n-num[u]);
51         }
52         else
53         {
54             dfs2(v,u);
55             dp[u] = max(dp[u],num[v]);
56         }
57     }
58 }
59 int main()
60 {
61     int i,u,v;
62     while(scanf("%d",&n)!=EOF)
63     {
64         e = 0;
65         for(i=1; i<=n; ++i)
66             head[i] = -1;
67         for(i=1; i<n; ++i)
68         {
69             scanf("%d%d",&u,&v);
70             addEdge(u,v);
71             addEdge(v,u);
72         }
73         dfs1(1,-1);
74         dfs2(1,-1);
75         int ans = INF;
76         for(i=1; i<=n; ++i)
77             ans = min(ans,dp[i]);
78         for(i=1; i<=n; ++i)
79             if(ans==dp[i])
80             {
81                 printf("%d",i);
82                 break;
83             }    
84         for(i+=1;i<=n; ++i)
85             if(ans==dp[i])
86                 printf(" %d",i);
87         puts("");
88 
89     }
90     return 0;
91 }

View Code

poj http://poj.org/problem?id=2378

给定n和n-1条边。

问删除哪些点使得最大的联通分支的结点个数小于总结点的一半。

和上面那题一样

 1 #include <stdio.h>
 2 #include <string.h>
 3 #include <stdlib.h>
 4 #include <algorithm>
 5 #include <iostream>
 6 #include <queue>
 7 #include <stack>
 8 #include <vector>
 9 #include <map>
10 #include <set>
11 #include <string>
12 #include <math.h>
13 using namespace std;
14 typedef long long LL;                   
15 const int INF = 1<<30;
16 const int N = 10000 + 10;
17 vector<int> g[N];
18 int num[N],dp[N];
19 int n;
20 void dfs1(int u, int fa)
21 {
22     num[u] = 1;
23     for(int i=0; i<g[u].size(); ++i)
24     {
25         int v = g[u][i];
26         if(v==fa) continue;
27         dfs1(v,u);
28         num[u] += num[v];
29     }
30 }
31 void dfs2(int u, int fa)
32 {
33     dp[u] = 0;
34     for(int i=0; i<g[u].size(); ++i)
35     {
36         int v = g[u][i];
37         if(v==fa)
38         {
39             dp[u] = max(dp[u],n-num[u]);
40         }
41         else
42         {
43             dp[u] = max(dp[u],num[v]);
44             dfs2(v,u);
45         }
46     }
47 }
48 int main()
49 {
50     int u,v,i;
51     while(scanf("%d",&n)!=EOF)
52     {
53         for(i=1; i<=n; ++i)
54             g[i].clear();
55         for(i=1; i<n; ++i)
56         {
57             scanf("%d%d",&u,&v);
58             g[u].push_back(v);
59             g[v].push_back(u);
60         }
61         dfs1(1,-1);
62         dfs2(1,-1);
63         int half = n / 2;
64         bool flag = false;
65         for(i=1; i<=n; ++i)
66             if(dp[i] <= half)
67             {
68                 flag = true;
69                 printf("%d
",i);
70             }
71         if(!flag)
72             puts("NONE");
73     }
74     return 0;
75 }

View Code

poj3140 http://poj.org/problem?id=3140

给定n个结点，m条边。

给定n个结点的权值

给定m条边

要求我们删除一条边，树分为两个部分，要求两个部分的权值之差最小。

思路：两次dfs，第一次dfs求出以该结点为根结点的子树的权值

　　　　第二次dfs枚举删除哪条边，然后记录树的两个部分的差值

　　　　最后一次遍历，找出最小的差值即可

 1 #include <stdio.h>
 2 #include <string.h>
 3 #include <stdlib.h>
 4 #include <algorithm>
 5 #include <iostream>
 6 #include <queue>
 7 #include <stack>
 8 #include <vector>
 9 #include <map>
10 #include <set>
11 #include <string>
12 #include <math.h>
13 using namespace std;
14 typedef __int64 LL;                   
15 const int INF = 1<<30;
16 const LL LLINF = ((LL)1)<<62;
17 const int N = 100000 + 10;
18 vector<int> g[N];
19 LL val[N];
20 LL dp[N];
21 LL sum;
22 //题意：分成两个部分，使得两个部分的权值之差尽可能小
23 void dfs1(int u, int fa)
24 {
25     for(int i=0; i<g[u].size(); ++i)
26     {
27         int v = g[u][i];
28         if(v==fa) continue;
29         dfs1(v,u);
30         val[u] += val[v];//求出以u为根结点的子树的权值之和
31     }
32 }
33 LL myAbs(LL a)
34 {
35     if(a < 0)
36         return -a;
37     return a;
38 }
39 void dfs2(int u, int fa)
40 {
41     dp[u] = sum;
42     for(int i=0; i<g[u].size(); ++i)
43     {
44         int v = g[u][i];
45         if(v==fa)
46         {
47             continue;
48         }
49         else//枚举删除边，然后用dp[u]记录最小值
50         {
51             dp[u] = min(dp[u],myAbs(sum-val[v]-val[v]));
52             dfs2(v,u);
53         }
54     }
55 }
56 int main()
57 {
58     int n,m;
59     int i,u,v;
60     int t = 1;
61     while(scanf("%d%d",&n,&m),n)
62     {
63         sum = 0;
64         for(i=1; i<=n; ++i)
65         {
66             g[i].clear();
67             scanf("%I64d",&val[i]);
68             sum += val[i];
69         }    
70         for(i=0; i<m; ++i)
71         {
72             scanf("%d%d",&u,&v);
73             g[u].push_back(v);
74             g[v].push_back(u);
75         }
76         dfs1(1,-1);
77         dfs2(1,-1);
78         LL ans = sum;
79         for(i=1; i<=n; ++i)
80             ans = min(ans,dp[i]);
81         printf("Case %d: %I64d
",t++,ans);
82 
83     }
84     return 0;
85 }

View Code

树形背包类:

选或者不选的01背包类型，那么每个点枚举容量，同时为下一个点枚举容量即可

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

给定n个洞穴和m个士兵（每个士兵能消灭20个bugs）

然后给定每个洞穴的bugs数量（背包的费用）和brain的数量（背包的价值）

然后给定n-1条边，使得n个洞穴形成一课树

问能取得的brain数量的最大值。

思路：其实就是在树上面进行背包问题的求解，只不过是有依赖的背包（儿子要选，当且仅当父亲也被选）

题解：http://www.cnblogs.com/justPassBy/p/4437436.html

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

思路：如果a=0，那么就建立一个根结点，让它指向a=0的结点。那么就可以变成一棵树了（同时m++）

变成树，每个结点选或者不选，就是01背包类型的树形dp，和上面那题一样

题解：http://www.cnblogs.com/justPassBy/p/4437849.html

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

题意是给定一棵树，每个结点有一个价值，要我们选择任意个结点使得总价值最大，规则是如果父亲结点被选了，那么儿子结点不可以被选，但是儿子的儿子可以被选

dp[u][1] 表示选择结点u可以获得的最大价值

dp[u][0]表示不选择结点u可以获得的最大价值

状态转移方程是 dp[u][1] = max( dp[u][1], dp[u][1]+dp[v][0] ); dp[u][0] = max( dp[u][0],max(dp[u][0]+dp[v][1], dp[u][0]+dp[v][0]) );

题解：http://www.cnblogs.com/justPassBy/p/4439068.html