pku 2486 apple tree

解法：

/////////////////////////////////////////////////////////////////////
//Apple Tree
//數(shù)組二維go，bk
//go[t][i]代表節(jié)點(diǎn)t的所有子樹(shù)上走i步不返回,取得的最大蘋果數(shù)
//bk[t][i]代表節(jié)點(diǎn)t的所有子樹(shù)上走i步并返回,取得的最大蘋果數(shù)
//求節(jié)點(diǎn)為x，實(shí)行不斷合并子樹(shù)求最優(yōu)值
//當(dāng)前合并到了q棵子樹(shù)：
//go[x][i]就是這q棵子樹(shù)上走i步不返回的最優(yōu)值
//bk[x][i]就是這q棵子樹(shù)上走i步并返回的最優(yōu)值
//合并第q+1棵子樹(shù)(不妨設(shè)第q+1棵子樹(shù)的根為y)的時(shí)候，有
//go[x][i] = max( bk[x][j]+go[y][i-j], bk[y][j]+go[x][i-j] ), j=0.....i
//bk[x][i] = max( bk[x][j]+bk[y][i-j] ) j=0,.....i;
////////////////////////////////////////////////////////////////////////////

代碼：http://www.shnenglu.com/qywyh/articles/18618.html