有一棵有n个点n-1条边的有根树，给出点权，要从中选出若干个点，保证其中任何两个点不再同一条边的端点上，求点权之和的最大值，\(1<=N<=6000\)。
解
本题树已经给出根，但是一定要有意识对于树的问题，转换成有根树，尤其是二叉树，可以大大简化问题。
本题显然为树形递推题，必然要表现节点这一状态，并且还有不能在同一边上的限制，于是设\(f[x][0/1]\)分别表示以x为根节点的子树中x选和不选的最大点权纸和，设\(x_i\)为x的第i个儿子,因此不难有
\[f[x][0]=\sum_{i=1}^{|son(x)|}\max(f[x_i][0],f[x_i][1])\]
\[f[x][1]=\sum_{i=1}^{|son(x)|}f[x_i][0]\]
边界：\(f[i][0]=\)对应点权,i为叶子节点编号，其余为0.
答案：\(max(f[r][0],f[r][1])\),r为根节点
参考代码：
dfs
#include <iostream>
#include <cstdio>
#define il inline
#define ri register
using namespace std;
struct point{
point *next;int to;
}*head[6001],*pt;
int h[6001],dp[6001][2],in[6001];
il int max(int,int);
il void read(int&),link(int,int),dfs(int);
int main(){
int n,root;read(n);
for(int i(1);i<=n;++i)read(h[i]);
for(int u(1),v(1);u&&v;)read(u),read(v),link(v,u),++in[u];
for(int i(1);i<=n;++i)if(!in[i]){root=i;break;}
dfs(root),printf("%d",max(dp[root][0],dp[root][1]));
return 0;
}
il int max(int a,int b){
return a>b?a:b;
}
il void dfs(int a){
for(point *i(head[a]);i!=NULL;i=i->next)
dfs(i->to),dp[a][0]+=max(dp[i->to][0],dp[i->to][1]),
dp[a][1]+=dp[i->to][0];dp[a][1]+=h[a];
}
il void link(int u,int v){
pt=new point,pt->to=v;
pt->next=head[u],head[u]=pt;
}
il void read(int &x){
x&=0;ri char c;while(c=getchar(),c==' '||c=='\n'||c=='\r');
ri bool check(false);if(c=='-')check|=true,c=getchar();
while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
if(check)x=-x;
}
bfs
#include <iostream>
#include <cstdio>
#include <queue>
#define il inline
#define ri register
using namespace std;
queue<int>T;
int h[6001],dp[6001][2],in[6001],
n,pa[6001];
il void read(int&);
il int max(int,int),dag();
int main(){
read(n);for(int i(1);i<=n;++i)read(h[i]);
for(int u(1),v(1);u&&v;)
read(u),read(v),pa[u]=v,++in[v];
printf("%d",dag());
return 0;
}
il int dag(){
for(int i(1);i<=n;++i)if(!in[i])T.push(i),dp[i][1]=h[i];
while(!T.empty()){
int s(T.front());T.pop();
dp[pa[s]][0]+=max(dp[s][0],dp[s][1]);
dp[pa[s]][1]+=dp[s][0],--in[pa[s]];
if(!in[pa[s]])dp[pa[s]][1]+=h[pa[s]],T.push(pa[s]);
}int root;for(root=1;root<=n;++root)if(!pa[root])break;
return max(dp[root][0],dp[root][1]);
}
il int max(int a,int b){
return a>b?a:b;
}
il void read(int &x){
x&=0;ri char c;while(c=getchar(),c==' '||c=='\n'||c=='\r');
ri bool check(false);if(c=='-')check|=true,c=getchar();
while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
if(check)x=-x;
}