想了解一下树形dp，可惜网上没有太好的入门教程，就从自己oj上发现了一道简单树形dp题，对着题解学习了一下
这个dp就是dfs变形啊，暴力啊，将所有可能的情况都跑一遍，选择这一点或者不选择，但还是有些技巧可言，比如dp[i][0]和dp[i][1]分别表示选择和不选择该结点，省去了很多记录的麻烦，递归到最后终点就是max(dp[1][0], dp[1][1])，熟悉递归的过程后还是很容易理解的，另外建树是通过vector，遍历起来很方便，唯一的疑惑就是不知道为什么是建双向图（哪位大佬解释一下子不胜感激啊），感觉单向完全够用了。。只能理解为无向图就双向建边这样子吧。
另外从网上找了树形dp介绍，感觉第四点就是说给我听的啊。。。：
1、什么是树型动态规划
顾名思义，树型动态规划就是在“树”的数据结构上的动态规划，平时作的动态规划都是线性的或者是建立在图上的，线性的动态规划有二种方向既向前和向后，相应的线性的动态规划有二种方法既顺推与逆推，而树型动态规划是建立在树上的，所以也相应的有二个方向：
1、叶－>根：在回溯的时候从叶子节点往上更新信息
2、根 - >叶：往往是在从叶往根dfs一遍之后（相当于预处理），再重新往下获取最后的答案。
不管是 从叶－>根 还是 从 根 - >叶，两者都是根据需要采用，没有好坏高低之分。
2、树形动态规划的优美之处
树真的是一种特别特别优美的结构！用来做动态规划也简直是锦上添花再美不过的事，因为树本身至少就有“子结构”性质（树和子树）；也本身就具有递归性。所以在树上DP其实是其所当然的事，相比线性动态规划来讲，转移方程更直观，更易理解。
3、难点
1、和线性动态规划相比，树形DP往往是要利用递归的，所以对递归不熟悉的同学，是一道小小的障碍，说是小小的，因为要去理解也不难。
2、细节多，较为复杂的树形DP，从子树，从父亲，从兄弟……已经一些小的要处理的地方，脑子不清晰的时候做起来颇为恶心
3、状态表示和转移方程，也是真正难的地方。做到后面，树形DP的老套路都也就那么多，难的还是怎么能想出转移方程，状压DP、概率DP这些特别的DP应该说做到最后都是这样！
4、补充
建有向图还是无向图？ 一般来说我们做树DP都是从上往下递归，如果不乱搞是不会从子节点往根节点的遍历的，这时候可以建有向图，只加边一次就可以，对于有“思想洁癖”的人来说，如果加一次边就可以再让他加两次是很难受的。但是有些题目可能很隐蔽的某个地方涉及到从子节点往上访问，就会错的很惨。所以，一般不非常确定建有向图就可的话还是建无向图吧。
#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<vector>
#include<set>
#include<map>
#include<queue>
#include<cmath>
using namespace std;
vector<int>v[100005];
int dp[100005][2];
void dfs(int cur, int fa)
{
for(int i = 0; i < v[cur].size(); i ++)
{
int son = v[cur][i];
if(son == fa) continue;
dfs(son, cur);
dp[cur][1] += dp[son][0];
dp[cur][0] += max(dp[son][0], dp[son][1]);
}
}
int main()
{
int n;
scanf("%d",&n);
for(int i = 1; i <= n; i ++){
scanf("%d",&dp[i][1]);
dp[i][0] = 0;
}
for(int i = 1; i <= n - 1; i ++)
{
int u, vv;
scanf("%d%d",&u,&vv);
v[u].push_back(vv);
v[vv].push_back(u);
}
dfs(1, 0);
printf("%d\n",max(dp[1][0], dp[1][1]));
return 0;
}