一道入门的树形DP。
首先我们对于数据进行有序化处理，这便于我们利用数据结构特点（可排序性）来发觉数据性质（有序、单调、子问题等等性质），以便于后续的转化、推理和处理。有序化可以“转化和创造”性质
首先将视角从无根树切换为有根树，这样我们就可以得到一个带有最优子结构、无后效性、子问题重叠性的结构——一个根和一堆子树。
由于我们是要求联通分量的最大值，我们观察到每一个联通分量都可以看做一个有根树，这就保证了树形DP的正确性。（后面会再解释）
不难想到令(f_i)表示包含该位置的、以(i)号节点为根的子树的最大值。
这里的“不难想到”其实有两种想法——第一种是树形DP的一般思路就是子啊一棵子树内处理根与子树的关系，这是一种常见的经验或者说手法。第二种想法就是说，连通分量可以转化成更小的联通分量，加上有序化之后，变成了子树层层求解。
我们考虑每一棵子树，不难发现初始化每个节点就是根节点自己的值，然后对于每一棵向下连接根节点的子树的最大值，如果大于零，那么我们就把根通向这棵子树的边连接起来。
令(j)为(i)子树根节点的编号，有$f_i = sum f_j times [f_j > 0] $
关于正确性，可能会有问题：对于一棵子树而言，我们只考虑了这些向下的分支，并没有考虑向上父节点的这支“分支”，感觉不太对劲？
实际上，我们要明确我们这里求的是一个小范围内子问题的最优解，不是全局最优解。如果每个点都考虑所有的分支情况（包括向上找父亲的那个分支），那么所有的点都是在求全局最优解，这样就无法进行DP或者状态转移了， 问题也没有得到简化。
我们考虑所谓“向上”的分支，实际上就是上面“向下”的分支，所以这种情况显然是可以被覆盖到的。如果上面的向下伸的这个分支是断的，没有到达这个子树的根节点，那么这棵子树加上向上一段的分支最大也会是负的，显然单独的子树或者单独的上面那个点都是更优的，不会有贡献。
实际上，我们陷入这种思维泥潭的主要原因还是不清楚DP的逻辑——DP的局部最优解是为全局服务的，这个局部最优解是在某种定义下成立的，不代表全局最优，但是可以求出全局最优。就比如这道题里面的局部最优解就不包括向上的分支，它只考虑这一棵子树内的情况，这样保证了问题的规模从小到大，保证了其他可以DP的性质。
思考DP算法，某种意义上而言，是一种构建数学和逻辑的“自动机”的过程。
DP可以从经验出发，可以从DP性质出发， 也可以从问题本身的性质出发，三者相互联系，加上一些转化或者优化的技巧可以求解。
总结：树形DP的一种一般分析方法是有序化（有根树）后考虑子树上跟和子树的关系转移；可以从小规模子问题入手；定义一种可以转移的状态（意义），并确定初始值和转移方法；时刻清楚讨论的问题和环境是什么，比如在局部最优中讨论整体最优就是无太大意义的，因为DP中不需要考虑
一种步骤：转化、子问题、状态、转移方程、优化
要格外注意递归中的“回头找”和计算和的关系。在这里是，不能把判断vis放到开头，不但多递归一层，就会多计算一层和。
源码：
#include <bits/stdc++.h>
#define N (int)(16005)
using namespace std;
typedef long long LL;
LL a[N];
vector<int> e[N];
LL f[N];
LL ans;
bool vis[N];
void dfs(int p)
{
ans = max(ans,f[p]);
vis[p] = true;
vis[p] = true;
//cout << p << "n";
for(int i = 0;i < e[p].size();i++)
{
int q = e[p][i];
if(vis[q]) continue;
dfs(q);
//cout << p << " " << q << " " << f[p] << " " << f[q] << "n";
if(f[q] > 0) f[p] += f[q];
ans = max(ans,f[p]);
}
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
int n;
cin >> n;
memset(f,0x8f,sizeof(f));
memset(vis,0,sizeof(vis));
ans = -1e18;
for(int i = 1;i <= n;i++)
{
cin >> a[i];
f[i] = a[i];
}
for(int i = 1;i <= n-1;i++)
{
int x,y;
cin >> x >> y;
e[x].push_back(y);
e[y].push_back(x);
}
dfs(1);
cout << ans << "n";
return 0;
}
文章来源: 博客园
- 还没有人评论，欢迎说说您的想法！
客服
