博客

一道没有陷阱的题目。

解题思路：对于树的问题。第一步肯定要先规定根。我们规定结点1为树的根。假设存在一个能获得最大利益的子树，那么这个子树的根肯定是其中的某个结点。所以，只要算出每个节点作为根时能得到的最大利益，问题就解决了。

用递归的dfs算。

#include <cstdio>
#include <vector>

using namespace std;

// 图 ======================================================{{{
struct Edge {
    Edge* next;
    int adj;
};


struct Graph {
    vector< Edge* > vs;

    void init(int vNum) {
        vs.resize(vNum);
        for (int i = 0; i < vs.size(); ++i) { vs[i] = NULL; }
    }

    Edge* newEdge() {
        return new Edge;
    }

    void add(int st, int ed) {
        Edge* e = newEdge();

        e->next = vs[st];
        vs[st] = e;
        e->adj = ed;
    }

    Edge* get(int i) {
    return vs[i];
    }
};

//=================================================== }}}

const char WHITE = 'W';
const char BLACK = 'B';
const char GRAY = 'G';

vector< char > color;
vector< int > profit;

int gBest;
int N;

Graph G;


//返回以结点id为根的最大利益子树的利益
int solve(int id) {
    color[id] = GRAY;

    Edge* e;
    int profitSum = profit[id];
    for (e = G.get(id); e; e = e->next) {
        if (color[e->adj] != WHITE) continue;
        int son = solve(e->adj);
        if (son > 0) profitSum += son;
    }

    color[id] = BLACK;

    if (profitSum > gBest) gBest = profitSum;
    return profitSum;
}


void input() {
    int i;
    scanf("%d", &N);
    profit.resize(N + 1);
    for (i = 1; i <= N; ++i) {
        int p;
        scanf("%d", &p);
        profit[i] = p;
    }

    G.init(N + 1);
    for (i = 1; i <= N - 1; ++i) {
        int start, end;
        scanf("%d %d", &start, &end);
        G.add(start, end);
        G.add(end, start);
    }

    gBest = -2000000000;
    color.resize(N + 1);
    for (i = 0; i < color.size(); ++i) color[i] = WHITE;
}

int main() {
    input();
    solve(1);
    printf("%d\n", gBest);
    return 0;
}


// vim:foldmethod=marker