【codevs1380】树形dp

#include <cstdio> #include <algorithm> using namespace std; const int MAXN = 6000 + 5; int n; int dp[MAXN][2]; struct Node { struct Edge *lastE; int v; int num; int fa; } N[MAXN]; struct Edge { Node *from, *to; Edge *next; Edge(Node *from, Node *to) : from(from), to(to), next(from->lastE) {} }; inline void addEdge(int u, int v) { N[u].lastE = new Edge(&N[u], &N[v]); N[v].fa = u; } void dfs(Node *v) { if (v->lastE != NULL) { for (Edge *e = v->lastE; e; e = e->next) { dfs(e->to); dp[v->num][1] += dp[e->to->num][0]; dp[v->num][0] += max(dp[e->to->num][0], dp[e->to->num][1]); } } } int main() { scanf("%d", &n); for (int i = 1; i <= n; i++) { N[i].num = i; scanf("%d", &N[i].v); } for (int i = 0; i < n - 1; i++) { int u, v; scanf("%d %d", &u, &v); addEdge(v, u); } int root; for (int i = 1; i <= n; i++) { dp[i][0] = 0; dp[i][1] = N[i].v; if (N[i].fa == 0) { root = i; } } dfs(&N[root]); printf("%d\n", max(dp[root][0], dp[root][1])); return 0; }

蒟蒻的第一道树形dp题[滑稽]，dp的题做得太少了