① poj2486/sicily1019 apple tree
② sicily1138 寻宝之旅
③ poj1947 Rebuilding Roads
④ poj2057 The Lost House
⑤ poj3140 Contestants Division
⑥ poj1655 Balancing Act
⑦ poj2378 Tree Cutting
最近做的几道TreeDP题，11-17切的几道都比较水，或者严格意义上来说都不算是TreeDP，或者有其他方法可以解。
七题大致可以分成两类：
一、①②③④
这四题属于一类，每题都有优美的状态转移方程。
从根结点出发后分为回到根结点与不回到根结点的情况
分为从根结点沿一条路与沿多条路出发的情况
分为包含根结点与不包含根结点的情况
分为遍历一棵树的最小期望和与遍历一棵树的步数
从上面可以得出，状态方程都是以当前子树的根结点为研究对象，包含了其所有的子树，必要的时候需要设立辅助方程。上面四题都是两个方程的。
二、⑤⑥⑦
树变森林问题。
这三题的大致意思就是挖去树中的某个点，或者某个边，形成森林，森林里的树有一些权值特征，然后就是对这些权值进行一些比较大小的操作，一般不要写状态方程，只是一个回溯统计的过程。
然后这三题规模都比较大，我是不喜欢用链表的，一开始我想用数组水过，多次无奈的尝试后，改用链表。
时间复杂度：
最外面一层属于Backtrack-free DFS，O(n)。
状态方程可能会达到O(n2)。
所以整个时间复杂度是属于平方或者立方级的。
空间复杂度：
规模大的开链表也可以满足了。
寻宝之旅 from sicily
Time limit: 10 second(s) Memory limit: 32768 KBytes
Total Submit : 99 Accepted Submit : 51
Problem
探险队长凯因意外的弄到了一份黑暗森林的藏宝图，于是，探险队一行人便踏上了寻宝之旅，去寻找传说中的宝藏。
藏宝点分布在黑暗森林的各处，每个点有一个值，表示藏宝的价值。它们之间由一些小路相连，小路不会形成环，即两个藏宝点之间有且仅有一条通路。探险队从其中的一点出发，每次他们可以留一个人在此点开采宝藏，也可以不留，然后其余的人可以分成若干队向这一点相邻的点走去。需要注意的是，如果他们把队伍分成两队或者两队以上，就必须留一个人在当前点，提供联络和通讯，当然这个人也可以一边开采此地的宝藏。并且，为了节约时间，队伍在前往开采宝藏的过程中是不会走回头路的。现在你作为队长的助理，已经提供了这幅藏宝图，请你算出探险队所能开采的最大宝藏价值。
Input
第一行有两个正整数n(1≤n≤100)表示藏宝点的个数，m（1≤m≤100）表示探险队的人数。
第二行是n个不超过100的正整数，分别表示1到n每个点的宝藏价值。
接下来的n-1行，每行两个数，x和y(1≤x,y≤n,x≠y)，表示藏宝点x,y之间有一条路，数据保证不会有重复的路出现。
假设一开始探险队在点1处。
Output
一个整数，表示探险队所能获得最大的宝藏价值。
Sample Input
Copy to clipboard
5 3
1 3 7 2 8
1 2
2 3
1 4
4 5
Sample Output
16
Problem Source: ZSUACM Team Member
/*
29
|
2008-11-14 16:26:27
|
0.05S
|
408K
|
C++
|
winsweet
|
差不多TreeDP的模板就是这个样子的了（美观考虑可以把输入，DFS，DP写成三个函数）。DFS里面加一个DP过程，DP也可以放在循环外面，即当前根结点的所有子树处理结束后，再计算根结点，譬如第④题（这题子树的排列是一个贪心的过程）。
Way和ways顾名思议就是上文里提到的分为从根结点沿一条路与沿多条路出发的情况。状态转移方程见红体字部分。
*/
#include <iostream>
#include <algorithm>
using namespace std;
const int N=101;
int n,m,w[N],t[N][N],ways[N][N],way[N][N];
void dfs(int k,int p) {
int ii,i,j,ts,t1[N],t2[N];
for (ii=1;ii<=t[k][0];ii++) {
ts=t[k][ii];
if (ts==p) continue;
dfs(ts,k);
//DP过程
t1[0]=t2[0]=0;
for (i=1;i<=m;i++) {
t1[i]=ways[k][i];
t2[i]=w[k];
}
for (i=1;i<=m;i++) for (j=1;j<=i;j++)
ways[k][i]=max(ways[k][i],max(t1[j]+ways[ts][i-j],t1[j]+way[ts][i-j]));
for (i=0;i<=m;i++) for (j=0;j<=i;j++)
way[k][i]=max(way[k][i],max(t2[j]+ways[ts][i-j],t2[j]+way[ts][i-j]));
}
}
int main() {
int x,y,i,j;
scanf("%d%d",&n,&m);
for (i=1;i<=n;i++) {
scanf("%d",&w[i]);
t[i][0]=0;
ways[i][0]=way[i][0]=0;
for (j=1;j<=m;j++) ways[i][j]=way[i][j]=w[i];
}
for (i=1;i<n;i++) {
scanf("%d%d",&x,&y);
t[x][++t[x][0]]=y;
t[y][++t[y][0]]=x;
}
dfs(1,0);
printf("%dn",max(ways[1][m],way[1][m]));
return 0;
}
Read More
,