树形DP用了分治的思想，先子树后合并。
树形DP的特点：每一个父亲的值都是由其各个儿子决定，采取记忆化搜索的形式来实现。That is, 树形DP就是一个后序遍历。
给出一个无根树，往往将节点1作为根，把其想象为一棵有根树。
HDU2196 computer.
分析：一棵树图，求出每个节点的单向出发所能达到的最远距离，边上权值为长度。
背包九讲说：记录每个节点的最长路的次长路及节点是由那个孩子回溯的到的。
代码清单：
#define _CRT_SECURE_NO_WARNINGS #include <cstdio> #include <cstring> #include <vector> #include <algorithm> using namespace std; const int N = 10007; struct Edge { int to, w; Edge(int to = 0, int w = 0):to(to), w(w){} }; vector<vector<Edge> > e; int n, fir[N], fir_id[N]; //最长路，fir_id记录最长路是由哪个孩子回溯得来的 int sec[N], sec_id[N]; //次长路 void dfs1(int u, int p) { //转化为有根树，求一下u为根的最长路 fir[u] = sec[u] = 0; for (Edge arc : e[u]) if(arc.to != p) { int v = arc.to; dfs1(v, u); //先深度到叶子，然后回溯时加权值 if (sec[u] < fir[v] + arc.w) { sec[u] = fir[v] + arc.w; sec_id[u] = v; if (sec[u] > fir[u]) { swap(sec[u], fir[u]); swap(sec_id[u], fir_id[u]); } } } } void dfs2(int u, int p) { for (Edge arc : e[u]) if (arc.to != p) { int v = arc.to; if (v == fir_id[u]) { //v是u最长路上的孩子 if (sec[v] < arc.w + sec[u]) { //更新次长路 sec[v] = arc.w + sec[u]; sec_id[v] = u; if (sec[v] > fir[v]) { swap(sec[v], fir[v]); swap(sec_id[v], fir_id[v]); } } //维护sec[]为此长路 } else { //更新最长路 if (sec[v] < arc.w + fir[u]) { sec[v] = arc.w + fir[u]; sec_id[v] = u; if (sec[v] > fir[v]) { swap(sec[v], fir[v]); swap(sec_id[v], fir_id[v]); } } } dfs2(v, u); } } int main() { while (~scanf("%d", &n)) { e.clear(); e.resize(n + 1); for (int i = 2; i <= n; ++i) { int to, w; scanf("%d%d", &to, &w); e[i].push_back(Edge(to, w)); e[to].push_back(Edge(i, w)); } dfs1(1, -1); //dfs1求以1为根的有向树的每棵子树的最长路fir[], sec[]为最次长路 dfs2(1, -1); for (int i = 1; i <= n; ++i) { printf("%d\n", fir[i]); } } return 0; }
二维背包 poj2576
#define _CRT_SECURE_NO_WARNINGS #include <cstdio> #include <cstring> #include <algorithm> using namespace std; const int N = 107; int w[N]; int dp[N * 450]; int main() { int n; while (~scanf("%d", &n)) { memset(dp, 0, sizeof dp); int sum = 0; for (int i = 1; i <= n; ++i) { scanf("%d", w + i); sum += w[i]; } int C = sum >> 1, m = n + 1 >> 1; dp[0] = 1; for (int i = 1; i <= n; ++i) { for (int j = C; j >= 0; --j) { //dp[]该体重下最少多少个人 if (dp[j] && dp[j] <= m && dp[j + w[i]] <= C) { if (dp[j + w[i]] == 0) dp[j + w[i]] = dp[j] + 1; else dp[j + w[i]] = min(dp[j + w[i]], dp[j] + 1); } } } for (int i = C; i >= 0; --i) if(dp[i]) { printf("%d %d\n", i, sum - i); break; } } return 0; }
