题解 P1122 【最大子树和】

· · 题解

基本思想：

很明显的是这是一道树形Dp，顺便带点贪心的思想。

我们设F[V]为根节点为V时最大子树和，此时F[V]由\Sigma_{E(V,u)}{F[V],F[V] + F[u]}决定。

但如果我们随便找一个根节点，直接去做这个Dp，很可能就会Wrong Answer。比如说Luogu给的样例，以1为根节点时。但直接这样Dp为什么他会错呢？

因为F[V]得到的是以V为根节点得到的最大子树和，所以F[V]一定包括了节点V的值。很显然如果这个根的值小于零，那他肯定不是最优的，所以要去根肯定大于零，而且应该根节点的值越大越好。

但是值最大的节点做根节点不一定能得到正确的答案，比如说以下这组：

5
3 -6 -4 2 2
1 2
1 3
2 4
4 5

我们贪心会得到3，而正确是4，QwQ，所以我睡觉时把我自己hack掉了，所以我们最后需要再找一遍根节点，或者Dp的时候记录一下。

部分代码解释

struct Graph {
    int Vertex;
    int Next;
} Edge[Maxn << 1]; //开两倍

void Read() {
    ~~~~~~~
    register int A, B;
    for (int i = 1; i < N; ++i) {
        A = Fscan();
        B = Fscan();
        Insert(A, B, Cnt, Head, Edge); //加边(u,v)
        Insert(B, A, Cnt, Head, Edge); //加边(v,u)
    }
}

树是双向边，记得加两次边(u,v) 和(v,u)，边集数组记得开两倍。

for (int i = 1; i <= N; ++i){
    Value[i] = Fscan();
    if(Value[i] > Value[S])
        S = i;
}

我们在读入的时候，找到值最大的节点，这样就不用在扫一遍记录值的数组了。

if (NV != P){
    Dfs(NV);
    F[V] = max(F[V], F[V] + F[NV]); //Dp QwQ
    //printf("%d %d %d\n",V,NV,F[V]);
}

因为这是一棵树，是双向边，所以Dfs时要判断一下，不然死循环就崩了。

代码

#include <cstdio>
#include <cstring>

#define max(A, B) A >= B ? A : B

const int INF = 0x7fffffff;
const int Maxn = 16000 + 5;

int Cnt, Head[Maxn];
int Value[Maxn];
struct Graph {
    int Vertex;
    int Next;
} Edge[Maxn << 1];

inline void Insert(const int &From, const int &To, int &Cnt, int *Head, Graph *Edge) {
    Edge[++Cnt].Vertex = To;
    Edge[Cnt].Next = Head[From];
    Head[From] = Cnt;
}

inline int Fscan() {
    char Ch = getchar();
    int X = 0, F = 1;
    while (Ch < '0' || Ch > '9') {
        if (Ch == '-')
            F = -1;
        Ch = getchar();
    }
    while ('0' <= Ch && Ch <= '9') {
        X = (X << 3) + (X << 1) + Ch - '0';
        Ch = getchar();
    }
    return X * F;
}

int N,S;

void Read() {
    N = Fscan();
    //printf("%d\n",N);
    for (int i = 1; i <= N; ++i){
        Value[i] = Fscan();
        if(Value[i] > Value[S])
            S = i;
    }

    //for(int i = 1; i <= N; ++i)
        //printf("%d ",Value[i]);
    //printf("\n");
    register int A, B;
    for (int i = 1; i < N; ++i) {
        A = Fscan();
        B = Fscan();
        Insert(A, B, Cnt, Head, Edge);
        Insert(B, A, Cnt, Head, Edge);
        //printf("%d %d\n",A ,B);
    }
    //printf("\n");
}

int F[Maxn];

void Dfs(const int &V,const int &P) {
    int NV;
    //printf(" %d %d\n",V,F[V]);
    F[V] = Value[V];
    for (int i = Head[V]; i; i = Edge[i].Next) {
        NV = Edge[i].Vertex;
        //printf(" %d ",NV);
        if (NV != P){
            Dfs(NV,V);
            F[V] = max(F[V], F[V] + F[NV]);
            //printf("%d %d %d\n",V,NV,F[V]);
        }
        //printf("%d\n",F[V]);
    }
    //printf("%d %d\n",V,F[V]);
    //F[V] = max(F[V], F[V] + Value[V]);
}

int main() {
    Read();
    Dfs(S,S);
    int Ans = -INF;
    for(int i = 1; i <= N; ++i)
        Ans = max(Ans, F[i]);
    printf("%d", Ans);
    //printf("%d", F[S]);
    //for(int i = 1 ; i <= N; ++i)
    //    printf("%d ",F[i]);
    return 0;
}