zrj2012-A3-0006

从 Trac 迁移的文章

这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。

原文章内容如下：

题目大意：给一个节点带权的数。对于每一个子树，子树内所有点的权值和记为这个子树的权值。当把一个节点删掉后，树会分成若干子树，求所有情况中，子树权值的乘积的最大值。
一个比较简单的树形DP，不妨以1为树根，先DFS构成树形结构，对于每一个节点，用f[i]表示以这个点为根的子树的权值。每个点被删除后，子树权值的乘积就是(f[son1]*f[son2]*....*f[sonk]*(f[1]-f[i])，本人是用高精度做的。不过单纯比较大小的话MS可以用取对数的方法，不过最后答案应该还是要高精度的。

题目大意：给一个节点带权的数。对于每一个子树，子树内所有点的权值和记为这个子树的权值。当把一个节点删掉后，树会分成若干子树，求所有情况中，子树权值的乘积的最大值。

一个比较简单的树形DP，不妨以1为树根，先DFS构成树形结构，对于每一个节点，用f[i]表示以这个点为根的子树的权值。每个点被删除后，子树权值的乘积就是(f[son1]*f[son2]*....*f[sonk]*(f[1]-f[i])，本人是用高精度做的。不过单纯比较大小的话MS可以用取对数的方法，不过最后答案应该还是要高精度的。