[Luogu] P1122 最大字段和 树形dp初探

前言

传送门 : https://www.luogu.com.cn/problem/P1122

不愧是 dp和树 两大结合 不是难一点 哈哈哈哈

思路

看完题目,画了一遍图,理解了题意

大概都知道了

f [ i ] f[i] f[i] 必然是一维状态转移 , 二维 ？ f [ i ] [ 2 ] f[i][2] f[i][2] 那么不选的时候 不是很没必要吗

因此我们考虑这个状态表示什么 :

根据以往的经验, 大概率表示 i 的 子 树 所 能 求 的 最 大 值 i的子树 所能求的最大值 i的子树所能求的最大值

因此我们可以很简单的知道状态转移方程 :

f [ i ] = m a x ( f [ j ] , 0 ) + a [ i ] ) f[i] = max(f[j],0) + a[i]) f[i]=max(f[j],0)+a[i])

CODE

#include 
using namespace std;
const int N = 1e4+6100;
const int INF  = 0x3f3f3f3f;
int f[N],a[N];
int e[N*2],ne[N*2],h[N*2],idx;

void add(int a,int b)
{
    e[idx] = b,ne[idx] = h[a],h[a] = idx++;
}
void dfs(int u ,int fa)
{
    f[u] = a[u];
    for(int i = h[u];i!=-1;i=ne[i])
    {
        int j = e[i];
        if(j!=fa)
        {
            dfs(j,u);
            if(f[j]>0)
            f[u]+=f[j];
        }
    }
}
void solve()
{
    int n;cin>>n;
    memset(h,-1,sizeof h);
    for(int i=1;i>a[i];

    for(int i=1;i>a>>b;
        add(a,b),add(b,a);
    }
    int res = -INF;
    dfs(1,0);
    for(int i=1;i