收集果子（树形dp）

题意： 给你一棵树，1为根节点，每个节点有果子数，每个节点的权值为其子树果子的和。问多少种删边的方式，使得1节点的权值为k。

思路： 组成k的种类数？？不就是多少种方法组成某个面值吗，可以想到是树上背包。定义f(i,j)为递归到第i个节点收集了j个果子的方案数。那么有两种子状态：(1)把(u,v)边断了，那么结果乘上p(size(u)-1) X f(u,i)。p(i)代表2的i次方。(2)加上以v节点代表的子树，那么结果就是f(u,i-j) X f(v,j).

但是极限数据拉到了1000，这个n^3的算法好理解，但是题解里面的n方算法还是没有理解完全（而且没法评测┭┮﹏┭┮）。

#include <cstdio>
#include <algorithm>
#include <algorithm>
using namespace std;
typedef long long ll;
const ll mod = 1e9 + 7;
ll a[1005];
ll f[1005][1005],g[1005],p[105],size[1005];
ll head[1005],nex[1005],to[1005],tot;
ll n,k;
void add(ll x,ll y)
{
to[++tot] = y;
nex[tot] = head[x];
head[x] = tot;
}
void dfs(ll u,ll fa)//n^3
{
size[u] = 1;
f[u][a[u]] = 1;
for(ll i = head[u];i;i = nex[i])
{
ll v = to[i];
if(v == fa)continue;
dfs(v,u);
size[u] += size[v];
for(ll i = 0;i <= k;i++)
{
g[i] = p[size[v] - 1] * f[u][i];
for(ll j = 0;j <= i;j++)
{
g[i] += f[u][i - j] * f[v][j] % mod;
}
}
for(ll i = 0;i <= k;i++)
{
f[u][i] = g[i];
}
}
}
void dfs2(ll u,ll fa)//n^2
{
size[u] = 1;
for(ll i = head[u];i;i = nex[i])
{
ll v = to[i];
if(v == fa)continue;
for(int j = 0;j + a[v] <= n;j++)//向下更新答案，类似线段树里面的pushdown
f[v][a[v] + j] = f[u][j];//此时定义为dfs到节点v,收集到i个节点的方案数
dfs(v,u);
size[u] += size[v];
for(int i = 0;i <= n;i++)//向上统计答案,类似线段树里面的pushup
{
f[u][i] = (p[size[v] - 1] * f[u][i] % mod + f[v][i]) % mod;
}
}
}
int main()
{
scanf("%lld%lld",&n,&k);
for(ll i = 1;i <= n;i++)
{
scanf("%lld",&a[i]);
}
for(ll i = 1;i <= n - 1;i++)
{
ll x,y;scanf("%lld%lld",&x,&y);
add(x,y);add(y,x);
}
p[0] = 1;
for(ll i = 1;i <= n;i++)p[i] = p[i - 1] * 2 % mod;
dfs(1,-1);
printf("%lldn",f[1][k]);
return 0;
}

（偶然看到的一道题，所以没有评测，原帖https://www.cnblogs.com/zbtrs/p/7779123.html）

最后

以上就是激昂寒风为你收集整理的收集果子（树形dp）的全部内容，希望文章能够帮你解决收集果子（树形dp）所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。