最大加权独立集问题

若加 权图 Ｇ＝ｆＶ，目的顶点集  的子集  中的任何 顶点  之间都不相邻 ，则称  为 图 Ｇ的独立集 ，顶点个数最多的独  立集称为最大独立 集。各顶点权 重之和最大 的独立集称为图  Ｇ的最大加权独立集 。如图 １所示 ，顶点集合 （４，３，１）是该图  的一个独立集， 且是最 大独立集 ，但不是最大加权独立集 。  顶点集合（５，２）是独立集，且是最大加权独立集 。最大加权独  立集 问题 已被证明为是个 ＮＰ完全问题。

一棵树，每个点有一个权值，选择一个权值最大的无父子节点点集。

关键词：树的最大”权值“独立集

f[i][0]：以i为根的子树不选根节点最大权值，

f[i][1]：以i为根的子树选根节点最大权值

f[u][1]+=f[v][0];

f[u][0]+=max(f[v][1],f[v][0]);

注：

1.若所有点的权值都大于0，则树的最大”权值“独立集也是极大点独立集，即任选两个点，一定有且仅有一个在该集合中。若存在点的权值小于0，则不一定成立。

变题：选择一个无祖先与后代节点的最大权值点集

f[u]:以i为根的子树的最大权值

f[u]=max{ w[u],sum{f[v]},v是u的孩子 } 两个选择：当前节点/后代，两个选择互斥

#include
#include
#include
#include
#include
#include
#include
#define ll long long
#define sf scanf
#define pf printf
#define maxn 10000
#define inf 0x3f3f3f
#define INF 1ll