树型DP基础题目总结树的最大独立集树的重心

65 阅读 0 评论 43 点赞

我是靠谱客的博主爱听歌钢铁侠，这篇文章主要介绍树型DP基础题目总结树的最大独立集树的重心，现在分享给大家，希望可以做个参考。

树的最大独立集

树的最大独立集被定义为：对于一棵n个结点的无根树，选出尽量多的结点，使得任意两个结点均不相邻。

输入数据：

结点数N
无向边N-1条

输出数据：

树的最大独立集为哪些点

用d[i]表示以i为根节点的子树的最大独立集大小。
那么对于结点i有两种策略：选和不选。
- 若选结点i，那么结点i的儿子就不能选了，只能选结点i的孙子。
- 若不选结点i，那么结点i的儿子就可以选。

复制代码

1
2
3
d[i] = max(1 + sum(d[j]),sum(d[k]));
//结点j为结点i的孙子集合
//结点k为结点i的儿子集合

复制代码

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <vector>
#include <iostream>
using namespace std;
/*
11
0 1
1 2
2 3
2 4
2 5
3 6
3 7
4 8
4 9
5 10
*/
const int maxn=1000;
const int INF=1e9;
vector<int>G[maxn];
int dp[maxn];//dp[i]表示以i为根的 子树 的最大独立集的数量
int dp1[maxn];
int n;
void ReadTree()
{//输入n-1条边
scanf("%d",&n);
for(int i=0;i<n-1;i++)
{
int s,e;
scanf("%d%d",&s,&e);
G[s].push_back(e);
G[e].push_back(s);
}
}
void zwh_dfs(int v,int father){
printf("%d -> %d n",v,father);
int num_temp = 0;
dp[v] = 0;
dp1[v] = 1;
for(int i = 0; i < G[v].size(); i++){
//第i个与v相连的点为G[v][i]
if(G[v][i]!=father){//第一个判断：V的下一步不能是father
zwh_dfs(G[v][i],v);
dp[v] += dp[G[v][i]];
}
for(int j = 0;j<G[G[v][i]].size();j++){
if(G[v][i]!=father && G[G[v][i]][j]!=v){//第二个判断：V的下一步的下一步不能是V
//第j个与G[v][i]相连的点为G[G[v][i]][j]
zwh_dfs(G[G[v][i]][j],G[v][i]);
dp1[v] += dp[G[G[v][i]][j]];
}
}
}
dp[v] = max(dp[v],dp1[v]);
}
int main()
{
ReadTree();
memset(dp,0,sizeof(dp));
zwh_dfs(0,-1);
for(int i = 0 ;i<n; i++) printf("dp[%d]:%dn",i,dp[i]);
return 0;
}

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
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <vector>
#include <iostream>
using namespace std;
/*
11
0 1
1 2
2 3
2 4
2 5
3 6
3 7
4 8
4 9
5 10
*/
const int maxn=1000;
const int INF=1e9;
vector<int>G[maxn];
int dp[maxn];//dp[i]表示以i为根的 子树 的最大独立集的数量
int dp1[maxn];
int n;
void ReadTree()
{//输入n-1条边
scanf("%d",&n);
for(int i=0;i<n-1;i++)
{
int s,e;
scanf("%d%d",&s,&e);
G[s].push_back(e);
G[e].push_back(s);
}
}
void zwh_dfs(int v,int father){
printf("%d -> %d n",v,father);
int num_temp = 0;
dp[v] = 0;
dp1[v] = 1;
for(int i = 0; i < G[v].size(); i++){
//第i个与v相连的点为G[v][i]
if(G[v][i]!=father){//第一个判断：V的下一步不能是father
zwh_dfs(G[v][i],v);
dp[v] += dp[G[v][i]];
}
for(int j = 0;j<G[G[v][i]].size();j++){
if(G[v][i]!=father && G[G[v][i]][j]!=v){//第二个判断：V的下一步的下一步不能是V
//第j个与G[v][i]相连的点为G[G[v][i]][j]
zwh_dfs(G[G[v][i]][j],G[v][i]);
dp1[v] += dp[G[G[v][i]][j]];
}
}
}
dp[v] = max(dp[v],dp1[v]);
}
int main()
{
ReadTree();
memset(dp,0,sizeof(dp));
zwh_dfs(0,-1);
for(int i = 0 ;i<n; i++) printf("dp[%d]:%dn",i,dp[i]);
return 0;
}

树的重心

树的重心被定义为：对于一棵n个结点的无根树，找到一个点，使得把树变成以该点为根的有根树的时候，最大子树的结点数最小。

输入数据：

结点数N
无向边N-1条

输出数据：

重心为哪个点
最大子树的结点数

对无根树进行DFS，求取每个结点对应的最大子树的节点数，最后使这个值最小即可。

复制代码

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <vector>
#include <iostream>
using namespace std;
const int maxn=1000;
const int INF=1e9;
vector<int>G[maxn];
int son[maxn];//son[i]表示以i为根的子树的节点个数(不包括根)
int ans,n,balance;
void ReadTree()
{//输入n-1条边
scanf("%d",&n);
for(int i=0;i<n-1;i++)
{
int s,e;
scanf("%d%d",&s,&e);
G[s].push_back(e);
G[e].push_back(s);
}
}
void zwh_dfs(int v,int father){
int balance_temp = 0;
son[v] = 1;
int son_size = G[v].size();
for(int i = 0; i < son_size; i++){
//第i个与v相连的点为G[v][i]
if(G[v][i]!=father){
zwh_dfs(G[v][i],v);
son[v] += son[G[v][i]];
balance_temp = max(balance_temp,son[G[v][i]]);//求取点v相连的点中的最大结点的数目
}
}
balance_temp = max(balance_temp,n - son[v]);//与点v的父结点的那一部分比较一下
if(balance_temp < balance)
{
balance = balance_temp;
ans = v;
}
}
int main()
{
ReadTree();
memset(son,0,sizeof(son));
ans=0;balance=INF;
zwh_dfs(0,-1);
for(int i = 0 ;i<n; i++) printf("son[%d]:%dn",i,son[i]);
printf("重心节点： %dn平衡（最大子树最少节点数）： %d",ans,balance);
return 0;
}
/*
11
0 1
1 2
2 3
2 4
2 5
3 6
3 7
4 8
4 9
5 10
*/

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
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <vector>
#include <iostream>
using namespace std;
const int maxn=1000;
const int INF=1e9;
vector<int>G[maxn];
int son[maxn];//son[i]表示以i为根的子树的节点个数(不包括根)
int ans,n,balance;
void ReadTree()
{//输入n-1条边
scanf("%d",&n);
for(int i=0;i<n-1;i++)
{
int s,e;
scanf("%d%d",&s,&e);
G[s].push_back(e);
G[e].push_back(s);
}
}
void zwh_dfs(int v,int father){
int balance_temp = 0;
son[v] = 1;
int son_size = G[v].size();
for(int i = 0; i < son_size; i++){
//第i个与v相连的点为G[v][i]
if(G[v][i]!=father){
zwh_dfs(G[v][i],v);
son[v] += son[G[v][i]];
balance_temp = max(balance_temp,son[G[v][i]]);//求取点v相连的点中的最大结点的数目
}
}
balance_temp = max(balance_temp,n - son[v]);//与点v的父结点的那一部分比较一下
if(balance_temp < balance)
{
balance = balance_temp;
ans = v;
}
}
int main()
{
ReadTree();
memset(son,0,sizeof(son));
ans=0;balance=INF;
zwh_dfs(0,-1);
for(int i = 0 ;i<n; i++) printf("son[%d]:%dn",i,son[i]);
printf("重心节点： %dn平衡（最大子树最少节点数）： %d",ans,balance);
return 0;
}
/*
11
0 1
1 2
2 3
2 4
2 5
3 6
3 7
4 8
4 9
5 10
*/