有一棵 n 个节点的树，树上每个节点都有一个正整数权值。如果一个点被选择了，那么在树上和它相邻的点都不能被选择。求选出的点的权值和最大是多少？
第一行包含一个整数 n 。
接下来的一行包含 n 个正整数，第 i 个正整数代表点 i 的权值。
接下来一共 n-1 行，每行描述树上的一条边。
对于20%的数据， n <= 20。
对于50%的数据， n <= 1000。
对于100%的数据， n <= 100000。
权值均为不超过1000的正整数。
#include <cstdio> #include <iostream> #include <algorithm> #include <stdlib.h> #include <cstring> #include <vector> #define inf 100005 using namespace std; int w[inf];//记录各点权重 vector<int> G[inf]; int d[2][inf]; //d[1][i] 为取第i个节点的最大值 //d[0][i] 为不取 bool vis[inf]; int n;//节点个数 void dfs(int u) { vis[u] = 1; for (int i = 0; i < G[u].size(); i++) { int v = G[u][i];//u的第i个儿子 if (vis[v])continue; dfs(v); d[1][u] += d[0][v]; d[0][u] += max(d[0][v], d[1][v]); } d[1][u] += w[u]; } int main() { scanf("%d", &n); for (int i = 1; i <= n; i++) scanf("%d", &w[i]); int a, b; for (int i = 0; i < n - 1; i++) { scanf("%d %d", &a, &b); G[a].push_back(b); G[b].push_back(a); } dfs(1); cout << max(d[0][1], d[1][1]); return 0; }
原文：https://www.cnblogs.com/woxiaosade/p/10445842.html