POJ 2342链接
树形dp入门题，对于几乎没有接触树形dp的同学来说，是不错的练习题。
题目大意：
一棵有向树中，节点带权值 ，选择其中一些节点使得选择的总的节点权值最大，选择的规则是不能同时选择一个节点和他的直接父亲节点。
解题思路：
无疑是一个多决策问题，在多步决策中得到最优的答案。考虑dp，树形结构，树形dp 。
设计状态：
dp[i][0]表示没有选择该节点的最大价值和
dp[i][1]表示选择该节点的最大价值和 ，输入的时候就可以初始化
dp[i][0]=sigma(max(dp[son][0] ,dp[son][1]))
dp[i][1]=sigma(dp[son][0])
最后用dfs找每一个节点的孩子节点 。dfs从根节点出发，当地状态转移是从叶子节点开始的 。这一点好好理解 。
代码
//#include<bits/stdc++.h>
#include<iostream>
#include<algorithm>
#include<stdio.h>
#include<vector>
using namespace std;
const int N=6e3+10;
int dp[N][2];
int root[N];
vector<int>ve[N];
int n;
int rt;
void dfs(int u)
{for(int i=0; i<ve[u].size(); i++){int v=ve[u][i];dfs(v);dp[u][0]+=max(dp[v][0],dp[v][1]);dp[u][1]+=dp[v][0];}
}
int main()
{scanf("%d", &n);for(int i = 1; i <= n; i++)scanf("%d", &dp[i][1]);int x, y;for(int i = 1; i < n; i++){scanf("%d%d", &x, &y);ve[y].push_back(x);root[x] = 1; //这里是找根节点}scanf("%d%d", &x, &y);for(int i=1; i<=n; i++){if(root[i]!=1){rt=i;break;}}dfs(rt);printf("%d",max(dp[rt][1],dp[rt][0]));return 0;
}
