问题描述
有一棵 n 个节点的树,树上每个节点都有一个正整数权值。如果一个点被选择了,那么在树上和它相邻的点都不能被选择。求选出的点的权值和最大是多少?
输入格式
第一行包含一个整数 n 。
接下来的一行包含 n 个正整数,第 i 个正整数代表点 i 的权值。
接下来一共 n-1 行,每行描述树上的一条边。
输出格式
输出一个整数,代表选出的点的权值和的最大值。
样例输入
5 1 2 3 4 5 1 2 1 3 2 4 2 5
样例输出
12
样例说明
选择3、4、5号点,权值和为 3+4+5 = 12 。
数据规模与约定
对于20%的数据, n <= 20。
对于50%的数据, n <= 1000。
对于100%的数据, n <= 100000。
权值均为不超过1000的正整数。
思路:
树形动态规划问题最重要的两步首先是建树,然后是进行动态规划。
(1)这是一棵无根多叉树,可以采用邻接表法存储,为了避免指针的使用麻烦,采用数组来代替,用head[maxn]存储头结点编号,用list[2*manx].vex存放邻接点域,用list[2*maxn].next存放链域。
(2)由于无根,所以哪个节点都能当做根,用y[i]表示选择第i个根的权值和,用n[i]表示不选择第i个根的权值和,假设选择了第i个根,则不能选择它的孩子,假如不选择第i个根,则它的孩子可选可不选(即可以选择孩子也可以选择孙子)。
#include <cstdio>
#include <algorithm>
using namespace std;
const int maxn = 100000 + 5;
int m, cnt = 0;
int y[maxn] = {0}, n[maxn] = {0}, w[maxn], head[maxn] = {0}, vis[maxn] = {0};
struct ArcNode
{
int vex, next;
}list[2 * maxn];
//插入边,插成对称的
void Insert(int u, int v)
{
list[++cnt].vex = v;
list[cnt].next = head[u];
head[u] = cnt;
list[++cnt].vex = u;
list[cnt].next = head[v];
head[v] = cnt;
}
void Dp(int root)
{
vis[root] = 1;
for(int i = head[root]; i != 0; i = list[i].next)
{
if(vis[list[i].vex] == 0)
{
Dp(list[i].vex);
y[root] += n[list[i].vex];
n[root] += max(y[list[i].vex], n[list[i].vex]);
}
}
y[root] += w[root];
}
int main()
{
int i, j, u, v, ans;
scanf("%d", &m);
for(i = 1; i <= m; i++)
scanf("%d", &w[i]);
for(j = 1; j <= m - 1; j++)
{
scanf("%d%d", &u, &v);
Insert(u, v);
}
Dp(1);
ans = max(y[1], n[1]);
printf("%d\n", ans);
return 0;
}
扫码关注腾讯云开发者
领取腾讯云代金券
Copyright © 2013 - 2025 Tencent Cloud. All Rights Reserved. 腾讯云 版权所有
深圳市腾讯计算机系统有限公司 ICP备案/许可证号:粤B2-20090059 深公网安备号 44030502008569
腾讯云计算(北京)有限责任公司 京ICP证150476号 | 京ICP备11018762号 | 京公网安备号11010802020287
Copyright © 2013 - 2025 Tencent Cloud.
All Rights Reserved. 腾讯云 版权所有