题解 P1122 【最大子树和】

· · 题解

前言

代码实现以及代码细节，各位题解dalao都写得很详细了，蒟蒻更想说一些思路上的东西

类似好题？（多倍经验）

p1352没有上司的舞会

Solution

俗话说的好：遇到dp问题，一定先问自己三个问题：怎么设计状态？怎么写转移方程？怎么实现？我们就来一个一个讲：

状态设计

对于此题：删去一棵树的一些部分，使得剩余部分点权和最大。凭借灵敏的dp直觉，状态dp[i]表示以i为根的树最大权值和，状态就设计完成了；

转移方程

所谓dp，不可能天上掉答案，所以必须从子问题或其他问题转移过来，如何转移？从子树？灵光一闪！脑中闪现过一个设想，对于每一个子树进行决策时，如果对答案有贡献，计入答案。 否则就把这个子树砍掉就可以了，非常容易就可以推出状态转移方程：

F[u]+=max(0,F[v])其中v为u的儿子

状态转移方程就搞定了

实现

使用dfs进行更新，是非常简单的技巧

注意几点细节：转移过程中要注意随时更新答案，不然可能无法保证解的正确性。不要走回自己的父节点因为双向加边

代码

#include <bits/stdc++.h>

using namespace std;

const int maxn=16000;

int  cnt,n,tp[maxn],f[maxn],head[maxn],ans=-1000000;
struct edge{
    int next,to;
}e[maxn<<1];

inline int read(){
    int f=1,x=0;
    char c=getchar();
    while(c<'0'||c>'9'){
        if(c=='-')f=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9'){
        x=x*10+c-'0';
        c=getchar();    
    }
    return x*f;
}

inline void add(int u,int v){
    e[++cnt].next=head[u];
    e[cnt].to=v;
    head[u]=cnt;
}

inline void dfs(int now,int fa){
    for(int i=head[now];i;i=e[i].next){
        int v=e[i].to;
        if(v==fa)continue;
        dfs(v,now);
        f[now]+=max(0,f[v]);
    }
    ans=max(ans,f[now]）;
}

int main(){
    int qwq,qaq;
    n=read();
    for(int i=1;i<=n;i++){
        f[i]=read();
    }
    for(int i=1;i<n;i++){
        qwq=read();
        qaq=read();
        add(qwq,qaq);
        add(qaq,qwq）;
    }
    dfs(1,0);
    printf("%d",ans);
    return 0;
}

请不要尝试复制此份代码，否则你会直接CE