dp专题六--树形dp

自用笔记算法

dp专题六–树形dp

HDU 1502–树的最大独立集

Problem Description

Input

Output

Sample Input

Sample Output

题目要求

树的结构为人际关系 雇员和老班只能要求一个人 转换成树的最大独立集问题

参考AC代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
#include<iostream>
#include<algorithm>
#include<cstring>
#include<vector>
using namespace std;
#define maxn 6050
int dp[maxn][2];
int vis[maxn];
vector<int>e[maxn];
void dfs(int root)
{
	vis[root]=1;
	for(int i=0;i<e[root].size();i++)
	{
		if(!vis[e[root][i]])
		{
			dfs(e[root][i]);
			dp[root][0]+=max(dp[e[root][i]][1],dp[e[root][i]][0]);
			dp[root][1]+=dp[e[root][i]][0];
		}
	}
}
//状态转移方程：
//用dp[i][0]表示不选中i号，周围的都可以选的最大值，dp[i][1]表示选中i号，那么周围都不能选的最大值。
//dp[i][0]+=(dp[j][1],dp[j][0])
//dp[i][1]+=dp[j][0]
int main()
{
	/*freopen("input.txt","r",stdin);*/
	int n;
	while(scanf("%d",&n)!=EOF)
	{
		/*if(n==0)
			break;*/
		memset(vis,0,sizeof(vis));
		memset(dp,0,sizeof(dp));
		for(int i=1;i<=n;i++)
		{
			scanf("%d",&dp[i][1]);
			e[i].clear();
		}
		for(int i=1;i<=n;i++)
		{
			int u,v;
			scanf("%d%d",&u,&v);
			if(u==0&&v==0)
				break;
			e[u].push_back(v);
			e[v].push_back(u);
		}
		dfs(1);
		printf("%d\n",max(dp[1][1],dp[1][0]));  //第一个点取与不取两种情况取最大值
	}
	return 0;
}

HDU 4118–树形dp

Problem Description

Input

Output

Sample Input

Sample Output

题目要求

树的结构：点代表城市 权值为距离
开始时每个城市都有一个人 接着每个人都要移动 最后每个城市依然要保持1个人 求所有人移动的最大距离

参考AC代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
#include<iostream>
#include<algorithm>
#include<cstring>
#include<vector>
#define LL long long
#define maxn 100000+50
using namespace std;
struct node
{
	int to,w;
	node(int to,int w):to(to),w(w){}
};
vector<node>e[maxn];
int vis[maxn];
LL ans=0;      //注意答案开为LL型
int n;
int num[maxn];   //num记录该结点下的结点数
void dfs(int u)
{
	vis[u]=1;
	num[u]=1;    //每次访问一个结点时初始化为1
	for(int i=0;i<e[u].size();i++)
	{
		int next=e[u][i].to;
		if(!vis[next])
		{
			dfs(next);
			num[u]+=num[next];   //父节点的下结点数等于所有子结点数之和
			LL minnum=min(num[next],n-num[next]);  //找出这个结点两边 结点小的那一边的结点数
			ans+=e[u][i].w*minnum*2LL;  //该结点数×权值×2就是答案
		}
	}
}
//因为结点两边只有最小的那一边移动才能满足两边顺利移动
//例如一边结点数为a 另一边为b 假设a＜b 那么选取a b那一端也一定能找出a个点与之匹配
//ans需要乘以2是因为来回要走两次
int main()
{
	/*freopen("input.txt","r",stdin);*/
	int t;
	cin>>t;
	int flag=1;
	while(t--)
	{
		cin>>n;
		for(int i=0;i<=n;i++)
			e[i].clear();
		for(int i=1;i<n;i++)
		{
			int u,v,w;
			cin>>u>>v>>w;
			e[u].push_back(node(v,w));
			e[v].push_back(node(u,w));
		}
		ans=0;
		memset(num, 0, sizeof(num));  
		memset(vis, 0, sizeof(vis));  
		dfs(1);
		cout<<"Case #"<<flag++<<": "<<ans<<endl;
	}
	return 0;
}

POJ 1655–树的重心

Problem Description

Input

Output

Sample Input

Sample Output

题目要求

求出一棵树的重心和最大子树的最小结点数

参考AC代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
#include<iostream>
#include<cstring>
#include<vector>
#include<algorithm>
#include<climits>
#define maxn 20000+50
using namespace std;
vector<int>e[maxn];
int vis[maxn];
int son[maxn];
int ans,size;
int n;
void dfs(int cur)
{
	vis[cur]=1;
	son[cur]=1;      //son用来计算每个结点的子结点数
	int temp=0;
	for(int i=0;i<e[cur].size();i++)
	{
		int next=e[cur][i];
		if(!vis[next])
		{
			dfs(next);
			son[cur]+=son[next];    //深搜一个 该结点的子结点数+1
			temp=max(temp,son[next]);   //首先算出深搜下去的结点最大值
		}
	}
	temp=max(temp,n-son[cur]);   //此段代码需放在for循环外 表示搜到头后 逆向回头判断另一边是否更大
	if(temp<size||(temp==size&&cur<ans))   //找到最大子树后比较后其出结点最小值
	{                                //若结点数相同返回位置小的
		ans=cur;
		size=temp;
	}
}
int main()
{
	/*freopen("input.txt","r",stdin);*/
	int t;
	cin>>t;
	while(t--)
	{
		cin>>n;
		for(int i=0;i<=n;i++)
			e[i].clear();
		for(int i=1;i<n;i++)
		{
			int u,v;
			cin>>u>>v;
			e[u].push_back(v);
			e[v].push_back(u);
		}
		ans=INT_MAX,size=INT_MAX;   //初始化为最大值 因为要求最小值
		memset(vis,0,sizeof(vis));
		dfs(1);
		cout<<ans<<" "<<size<<endl;
	}
	return 0;
}

POJ 3107–树的重心

Problem Description

Input

Output

Sample Input

Sample Output

题目要去

求出树的所有重心后排序输出

参考AC代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
#include<iostream>
#include<cstring>
#include <algorithm>
#include<climits>
#define maxn 50000+50
using namespace std;
struct Edge        //此题卡时间 必须用前向星存图 使用vector会超时
{
	int to,next;
};
Edge edge[2*maxn];   //无向图开两倍
int head[maxn];
int vis[maxn];
int son[maxn];
int n,ans[maxn],size,num,cnt;
void add(int u,int v)
{
	edge[cnt].to = v;  
	edge[cnt].next = head[u];  
	head[u] = cnt++;  
}
void init()
{
	memset(vis,0,sizeof(vis));
	memset(head,-1,sizeof(head));
	size=INT_MAX;
	num=0;
	cnt=0;
}
void dfs(int cur)
{
	vis[cur]=1;
	son[cur]=1;
	int temp=0;
	for(int i=head[cur];i!=-1;i=edge[i].next)
	{
		int next=edge[i].to;
		if(!vis[next])
		{
			dfs(next);
			son[cur]+=son[next];
			temp=max(temp,son[next]);
		}
	}
	temp=max(temp,n-son[cur]);
	if(temp<size)  //与上题一样 区别在于用ans数组才存储重心
	{
		num=1;    //只要有比当前小的 ans和num均初始化
		ans[0]=cur;
		size=temp;
	}
	else if(temp==size)   //否则存入数组
		ans[num++]=cur;
}
int main()
{
	/*freopen("input.txt","r",stdin);*/
	while(scanf("%d",&n)!=EOF)
	{
		init();
		for(int i=1;i<n;i++)
		{
			int u,v;
			scanf("%d%d",&u,&v);
			add(u,v);
			add(v,u);
		}
		dfs(1);
		sort(ans,ans+num);
		for(int i=0;i<num;i++)
			printf("%d ",ans[i]);
		puts("");
	}
	return 0;
}

hihocoder 1050–树的直径

Input
每个测试点（输入文件）有且仅有一组测试数据。
每组测试数据的第一行为一个整数N，意义如前文所述。
每组测试数据的第2~N行，每行分别描述一根木棍，其中第i+1行为两个整数Ai，Bi，表示第i根木棍连接的两个小球的编号。
对于20%的数据，满足N<=10。
对于50%的数据，满足N<=10^3。
对于100%的数据，满足N<=10^5，1<=Ai<=N, 1<=Bi<=N
小Hi的Tip：那些用数组存储树边的记得要开两倍大小哦！

Output
对于每组测试数据，输出一个整数Ans，表示给出的这棵树中距离最远的两个结点之间相隔的距离。

Sample Input
8
1 2
1 3
1 4
4 5
3 6
6 7
7 8

Sample Output
6

参考AC代码（一）：两次dfs

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
//此题用了一个性质：随便找一个点 dfs搜索到最远位置 该点一定是直径中的一个点
//接着对该点再进行dfs搜索 得到的就是最大直径
#include<iostream>
#include<cstring>
#include<algorithm>
#include<vector>
#define maxn 100000+50
using namespace std;
vector<int>e[maxn];
int vis[maxn];
int n,p,ans;
void dfs(int deep,int root)
{
	if(deep>ans)     //取最深长度
	{
		ans=deep;
		p=root;    //p记录第一次走的最远位置
	}
	vis[root]=1;
	for(int i=0;i<e[root].size();i++)
	{
		int next=e[root][i];
		if(!vis[next])
			dfs(deep+1,next);
	}
}
int main()
{
	/*freopen("input.txt","r",stdin);*/
	while(scanf("%d",&n)!=EOF)
	{
		for(int i=0;i<=n;i++)
			e[i].clear();
		for(int i=1;i<n;i++)
		{
			int u,v;
			scanf("%d%d",&u,&v);
			e[u].push_back(v);
			e[v].push_back(u);
		}
		p=0,ans=0;
		memset(vis,0,sizeof(vis));
		dfs(0,1); 
		ans=0;               //第二次深搜注意初始化
		memset(vis,0,sizeof(vis));
		dfs(0,p);
		printf("%d\n",ans);
	}
	return 0;
}

参考AC代码（二）：使用fi+se后序遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
#include<iostream>
#include<cstring>
#include<algorithm>
#include<vector>
#define maxn 100000+50
using namespace std;
vector<int>e[maxn];
int vis[maxn];
int n,ans;
int dfs(int root)
{
	int fi=0,se=0,d;
	vis[root]=1;
	for(int i=0;i<e[root].size();i++)
	{
		int next=e[root][i];
		if(!vis[next])
		{
			d=dfs(next)+1;   //dfs返回的结果表示以next为根节点的子树的最长路径值
			if(d>fi)        //1加的是子树的根节点到next的长度
			{
				se=fi;    //d比fi大 都要更新
				fi=d;
			}
			else if(d>se)  //只比se大 更新se即可
				se=d;
		}
	}
	ans=max(ans,fi+se);
	return fi;
}
int main()
{
	/*freopen("input.txt","r",stdin);*/
	while(cin>>n)
	{
		for(int i=0;i<=n;i++)
			e[i].clear();
		for(int i=1;i<n;i++)
		{
			int u,v;
			cin>>u>>v;
			e[u].push_back(v);
			e[v].push_back(u);
		}
		memset(vis,0,sizeof(vis));
		ans=0;
		dfs(1);
		cout<<ans<<endl;
	}
	return 0;
}

HDU 2196–给定权求树的直径

Problem Description

Input

Output

Sample Input

Sample Output

题目要求

给定树的边权 对于树中的每个点 求出离该点的最远距离

参考AC代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
#include<iostream>
#include<cstring>
#include<algorithm>
#include<vector>
#define maxn 10000+50
using namespace std;
struct node
{
	int to,w;
	node(int to,int w):to(to),w(w){}
};
vector<node>e[maxn];
int n;
int dp[maxn][3];    //dp[i][0]表示以i为顶点的最大值 dp[i][1]表示以i为顶点的次大值
void dfs1(int root)    //dp[i][2]表示i的父节点部分获得的最大值
{
	int fi=0,se=0;
	int temp=0;
	for(int i=0;i<e[root].size();i++)
	{
		int next=e[root][i].to;
		dfs1(next);
		temp=dp[next][0]+e[root][i].w;
		if(temp>fi)
		{
			se=fi;
			fi=temp;
		}
		else if(temp>se)
			se=temp;
	}
	dp[root][0]=fi;      //与求树的一般直径相同 求出fi与se的值
	dp[root][1]=se;
}
void dfs2(int root)
{
	for(int i=0;i<e[root].size();i++)
	{
		int next=e[root][i].to;       //下式是dp[i][2]的状态转移方程 详情看解析
		dp[next][2]=max(dp[root][2],dp[next][0]+e[root][i].w==dp[root][0]?dp[root][1]:dp[root][0])+e[root][i].w;
		dfs2(next);
	}
}
int main()
{
	/*freopen("input.txt","r",stdin);*/
	while(cin>>n)
	{
		for(int i=0;i<=n;i++)
			e[i].clear();
		for(int i=2;i<=n;i++)
		{
			int p,w;
			cin>>p>>w;
			e[p].push_back(node(i,w));
		}
		dfs1(1);
		dp[1][2]=0;     //根没有父节点
		dfs2(1);
		for(int i=1;i<=n;i++)
			cout<<max(dp[i][0],dp[i][2])<<endl;
		
	}
	return 0;
}

思路


对于上面那棵树，要求距结点2的最长距离，那么，就需要知道以2为顶点的子树（蓝色圈起的部分，我们叫它Tree（2）），距顶点2的最远距离L1
还有知道2的父节点1为根节点的树Tree（1）-Tree(2)部分（即红色圈起部分），距离结点1的最长距离+dist(1,2) = L2，那么最终距离结点2最远的距离就是
max{L1，L2}

f[i][0],表示顶点为i的子树的，距顶点i的最长距离
f[i][1],表示顶点为i的子树的，距顶点i的次长距离
f[i][2],表示Tree(i的父节点)-Tree(i)的最长距离+i跟i的父节点距离

要求所有的f[i][0]和f[i][1]很简单，只要先做一次dfs求每个结点到叶子结点的最长距离和次长距离即可。
然后要求f[i][2], 可以从父节点递推到子节点，

假设节点u有n个子节点，分别是v1,v2…vn
那么
如果vi不是u最长距离经过的节点，f[vi][2] = dist(vi,u)+max(f[u][0], f[u][2])
如果vi是u最长距离经过的节点，那么不能选择f[u][0],因为这保存的就是最长距离，要选择Tree（u）第二大距离secondDist,
可得f[vi][2] = dist(vi, u) + max(f[u][1], f[u][2])

本文标题:dp专题六--树形dp

文章作者:Hippopmonkey

发布时间:2017-02-12, 21:54:30

最后更新:2017-02-14, 23:49:45

原始链接:http://xuboming8.github.io/2017/02/12/dp专题六-树形dp/

许可协议: "署名-非商用-相同方式共享 4.0" 转载请保留原文链接及作者。

文章目录
  1. 1. dp专题六–树形dp
    1. 1.1. HDU 1502–树的最大独立集
      1. 1.1.1. 题目要求
      2. 1.1.2. 参考AC代码
    2. 1.2. HDU 4118–树形dp
      1. 1.2.1. 题目要求
      2. 1.2.2. 参考AC代码
    3. 1.3. POJ 1655–树的重心
      1. 1.3.1. 题目要求
      2. 1.3.2. 参考AC代码
    4. 1.4. POJ 3107–树的重心
      1. 1.4.1. 题目要去
      2. 1.4.2. 参考AC代码
    5. 1.5. hihocoder 1050–树的直径
      1. 1.5.1. 参考AC代码（一）：两次dfs
      2. 1.5.2. 参考AC代码（二）：使用fi+se后序遍历
    6. 1.6. HDU 2196–给定权求树的直径
      1. 1.6.1. 题目要求
      2. 1.6.2. 参考AC代码
      3. 1.6.3. 思路
|