一颗树，选取不相邻的点，求最大点权值
因为当前结点选或不选后后效性，所以我们加一唯来取消后效性
表示以i为根的树且i不选的最大价值
表示以i为根的树且i选的最大价值
显然有
#include#include #include #define REP(i, a, b) for(int i = (a); i < (b); i++)using namespace std;const int MAXN = 6123;int f[2][MAXN], a[MAXN], b[MAXN], n;vector g[MAXN];void dfs(int u){ f[0][u] = 0; f[1][u] = a[u]; if(!g[u].size()) return; REP(i, 0, g[u].size()) { int v = g[u][i]; dfs(v); f[1][u] += f[0][v]; f[0][u] += max(f[0][v], f[1][v]); }}int main(){ scanf("%d", &n); REP(i, 1, n + 1) scanf("%d", &a[i]); int fa, son; while(~scanf("%d%d", &son, &fa) && fa) { g[fa].push_back(son); b[son] = 1; } REP(i, 1, n + 1) if(!b[i]) { dfs(i); printf("%d\n", max(f[0][i], f[1][i])); break; } return 0; }