# 111qqz的小窝

## hdu 1520 Anniversary party (树形dp模板题)

dp1[v]表示包含v节点的子树的最大值。

dp2[v]表示，不包含v节点的子树的最大值。

Now, similar to array problem, we have to make a decision about including node V in our subset or not. If we include node V, we can’t include any of its children(say v1, v2, …, vn), but we can include any grand child of V. If we don’t include V, we can include any child of V.

So, we can write a recursion by defining maximum of two cases.
.

As we see in most DP problems, multiple formulations can give us optimal answer. Here, from an implementation point of view, we can define an easier solution using DP. We define two DPs, and , denoting maximum coins possible by choosing nodes from subtree of node V and if we include node V in our answer or not, respectively. Our final answer is maximum of two case i.e. .

And defining recursion is even easier in this case. (since we cannot include any of the children) and (since we can include children now, but we can also choose not include them in subset, hence max of both cases).

cf682C题目链接

## hdu 2196 Computer (树的直径||树形dp)

hdu2196

1A.

20161201upd:更新一个dp的做法（虽然用树的直径搞貌似要更好想也更直观，不过为了体会dp的思想嘛。。。）

这道题要求的是从树上一点出发的最长路。考虑有根树，不难想到，从树上一点u出发的最长路必然是下述两种情况之一：
（1）第一步向下走，（一直向下，走到某叶子节点）
（2）第一步向上走。

dp[0][u] : 从节点u向下走的最长路径
dp[1][u] : 从节点u向下走的次长路径

dp[2][u] : 从节点u第一步向上走所能获得的最长路径

（1）第二步向下走, 这样便转移到u的父亲节点f第一步向下走的情况。

（2）第二步仍向上走，这样便转移到f第一步向上走的情况，即dp[2][f]。

## poj 2342 Anniversary party (基础树形dp)

dp[i][0]和dp[i][1]分别表示第i个人不参加和参加party对应的val和。