题解 P1122 【最大子树和】

FCBM71 · 2019-12-01 19:20:45 · 题解

很不错的树形DP入门题，适合FCB这类的DP萌新练手。

审题永远是解决一道题目的第一步。本题的题干略显冗长，大概概括一下就是指：给定一棵树，求出他的点权之和最大的一颗子树的点权和。特别地，子树不能为空（貌似这里吊死了很多人）

思路分析

本题中只给出了每条边连接的节点编号，但是没有给出祖宗关系，于是我们就可以随意一点了，不妨假设1节点就是根节点。根节点确定祖宗关系也就随之确定了。（当然，只要你愿意，任意一个节点都可以作为根节点）

我的思路是两个转移方程同时进行。首先假设每个节点点权为 a[i]

$$\text{fy[i]=a[i]+}\Sigma\text{max(fy[i's sons],0)}$$
$$\text{fn[i]=max(fy[i's sons],fn[i's sons])}$$

最后的答案 max(fy[1],fn[1])
总时间复杂度 O(n) ，妥妥的。

代码实现

还是比较容易的，但是有几个对于萌新的坑点或者注意点

与绝大部分树形DP一样，它并不能线性循环实现，而是要通过从根节点开始递归，直到叶节点再开始回溯。
本题的数据范围达到了 \text{16000} ，个人建议使用链式前向星存边。特别地，本题由于无法直接确定父子关系，所以加边时要双向加边。因此在 dfs 的时候也要注意不能从儿子返回搜索到了父亲。
fn 数组要出事化成一个极小值，用来应付所有点权都是负数的情况

inline void tomax(int &a,int b){if(a<b)a=b;} //手写max可以加速

void dfs(int x,int fa){
    for(int i=head[x];i;i=nxt[i]){   //链式前向星的访问
        if(to[i]==fa)continue;    //不能搜向父亲
        dfs(to[i],x);      //向儿子递归
        if(fy[to[i]]>0)fy[x]+=fy[to[i]];   //状态转移
        tomax(fn[x],fn[to[i]]);
        tomax(fn[x],fy[to[i]]);
    }
}

完整代码

代码略丑，还望各位多多包涵

#include<cstdio>
#include<cstring>

const int N=16005;
int fy[N],fn[N],n,a[N],maxx;bool flag;
int nxt[N*2],to[N*2],head[N],num,x,y;  //记得开两倍

inline void add(int x,int y){
    to[++num]=y;nxt[num]=head[x];head[x]=num;  //加边
}

inline void tomax(int &a,int b){if(a<b)a=b;}

void dfs(int x,int fa){   //递归求解
    for(int i=head[x];i;i=nxt[i]){
        if(to[i]==fa)continue;
        dfs(to[i],x);
        if(fy[to[i]]>0)fy[x]+=fy[to[i]];
        tomax(fn[x],fn[to[i]]);
        tomax(fn[x],fy[to[i]]);
    }
}

int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;++i)
     scanf("%d",&a[i]),fy[i]=a[i];  //初始化1
    for(int i=1;i<n;++i){
        scanf("%d%d",&x,&y);
        add(x,y);add(y,x);    //加边
    }
    memset(fn,0x80,sizeof(fn));  //初始化2
    dfs(1,0);  //求解
    printf("%d",fy[1]>fn[1]?fy[1]:fn[1]);
    return 0;
}