题解 P1122 【最大子树和】

一个昵称 · 2019-11-05 22:25:56 · 题解

一道树上DP题

这题其实挺简单的……

首先 我们可以很轻松的看出来 这道题和树有关 或者说 他是一个无向图 而且又是求最优解 那么 直接就上树上DP

先找状态转移方程 其实这里用上一个贪心的思想 就是 只有加上一个正的数 他的值才会高嘛 而且 只要值能变高 当然是加的越多越好 所以方程就是 f[i]+=max(0,f[j])

然后 树上DP其实都跟dfs差不多（我jio得差不多） 所以直接写一个dfs来更新答案就好啦

下面附上代码

#include<iostream>
using namespace std;

int vis[16001];

int head[16001];

struct nod{
    int to,nxt;
}e[32005];

int f[16001];

int n,cnt=0;

void addEdge(int u,int v){
    e[++cnt]=(nod){v,head[u]};
    head[u]=cnt;
}

void dfs(int s){
    vis[s]=1;
    for(int i=head[s];i;i=e[i].nxt){
        int v=e[i].to;
        if(vis[v]) continue;
        dfs(v);
        f[s]+=max(0,f[v]);
    }
}

int main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>f[i];
    }
    for(int i=1,u,v;i<n;i++){
        cin>>u>>v;
        addEdge(u,v);
        addEdge(v,u);
    }
    dfs(1);
    int ans=-999999999;
    for(int i=1;i<=n;i++){
        ans=max(ans,f[i]);
    }
    cout<<ans;
    return 0;
}