题解 P1122 【最大子树和】

linyinuo2008 · 2021-06-09 22:22:45 · 题解

原题链接

树形 \text{DP} 好题。

1、题意理解

给你一棵有 n 个节点的树，每个节点有一个点权，让你从中找出一棵子树，使得这棵子树上所有节点的点权和最大，求出这个最大值。

数据范围： 1 \leq n \leq 16000。

2、算法分析

从这里借两张图。

看样例，我们不难发现所说的“最大子树和”就在这里：

所以我们该怎样设计状态呢，很简单！就是树形 \text{DP} 标准状态设计法，我们设 f_u 表示以 u 为根节点的最大子树和。由于以 u 为根节点的最大子树必然包括 u 自己，所以初始化

然后我们遍历 u 的每一个子节点 v ，这里用到了一点贪心的思想，如果 f_v>0 ，也就是说以 v 为根节点的最大子树和大于零，那我就可以把这棵树上面接一个根节点 u 。

这样以 v 为根节点的最大子树就为以 u 为根节点的最大子树做出贡献，反之则不选，因为选了还得减，是个累赘。

结果： \max(f_i)

我们可以用vector来建树（常数这么小的东西咱们不用？），最后附上个树形 \text{DP} 模板送给大家：

void dfs(int u,int fa)
{
    Init();
    vis[u]=1;//有时要（可以）加，本题不用加 
    for(int i=0;i<tree[u].size();i++)
    {
        int nxt=tree[u][i];
        if(nxt!=fa&&!vis[nxt])
        {
            dfs(nxt,u);
            dp();
        }   
    }   
} 

3、代码

代码中有注释。

#include <iostream>
#include <vector>
using namespace std;
const int N=16005;
int a[N],n,f[N];//f[i]表示以i为根节点最大子树和
vector<vector<int> > tree(N);//vector建树 
void dfs(int u,int fa)//当前节点与其父亲节点 
{
    f[u]=a[u];//初始化为节点点权 
    for(int i=0;i<tree[u].size();i++)//遍历每个节点 
    {
        if(tree[u][i]!=fa)//不能往回搜父亲 
        {
            int nxt=tree[u][i];
            dfs(nxt,u);
            if(f[nxt]>0)
                f[u]+=f[nxt];//动归转移 
        }
    }
}
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
        cin>>a[i];
    for(int i=1;i<=n-1;i++)
    {
        int p,q;
        cin>>p>>q;
        tree[p].push_back(q);//无向边要push两次 
        tree[q].push_back(p);   
    } 
    dfs(1,0);//这里其实从任何一个节点开始搜都可以，因为是一次性的 
    int ans=-0x7f7f7f;
    for(int i=1;i<=n;i++)
        ans=max(ans,f[i]);//求结果 
    cout<<ans;
    return 0;
} 

若有错误，欢迎指出！