[勿忘国耻 振兴中华]
做完了以后才发现窝原来做过这道题?? 代码还特别短????

懵逼的 题目

传送至 Codevs

扯淡的 题解

对每一个节点都有选或者不选两种决策, 如果选就要求子节点不选, 否则子节点可选可不选

沙茶的 代码

After

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <vector>
#define INF (0x7ffffff)
#define MAXN (6000 + 5)
#define max(a, b) ((a) > (b) ? (a) : (b))
using namespace std;
int root;
struct mem
{
    int fa;
    vector <int> son;
    int ha;
} a[MAXN];
int n;
int f[MAXN][2];
int dfs(int, int);
int main()
{
    scanf("%d", &n);

    for(int i = 1; i <= n; i++)
    {
        a[i].fa = i;
        f[i][0] = f[i][1] = -INF;
        scanf("%d", &a[i].ha);
    }

    int srx, sry;

    for(int i = 1; i < n; i++)
    {
        scanf("%d%d", &srx, &sry);
        a[sry].son.push_back(srx);
        a[srx].fa = sry;
    }

    for(int i = 1; i <= n; i++)
    {
        if(a[i].fa == i)
        {
            root = i;
        }
    }

    dfs(root, 1);
    dfs(root, 0);
    printf("%d", max(f[root][1], f[root][0]));
    return 0;
}
int dfs(int dq, int cho)
{

    if(f[dq][cho] != -INF)
    {
        return f[dq][cho];
    }
    else
    {
        f[dq][cho] = 0;

        if(!a[dq].son.size())
        {
            if(cho)
            {
                return f[dq][cho] = a[dq].ha;
            }
            else
            {
                return f[dq][0] = 0;
            }
        }

        if(cho)
        {
            f[dq][cho] = a[dq].ha;
            for(int i = 0; i < a[dq].son.size(); i++)
            {
                if(f[a[dq].son[i]][0] == -INF)
                {
                    f[a[dq].son[i]][0] = dfs(a[dq].son[i], 0);
                }

                f[dq][cho] = max(f[dq][cho], f[dq][cho] + f[a[dq].son[i]][0]);
            }
        }


        if(!cho)
        {
            for(int i = 0; i < a[dq].son.size(); i++)
            {
                if(f[a[dq].son[i]][1] == -INF)
                {
                    f[a[dq].son[i]][1] = dfs(a[dq].son[i], 1);
                }
                if(f[a[dq].son[i]][0] == -INF)
                {
                    f[a[dq].son[i]][0] = dfs(a[dq].son[i], 0);
                }
                f[dq][cho] = max(f[dq][cho], max(f[dq][cho] + f[a[dq].son[i]][1], f[dq][cho] + f[a[dq].son[i]][0]));
            }
        }

        return f[dq][cho];
    }
}
/*
7
1
1
1
1
1
1
1
1 3
2 3
6 4
7 4
4 5
3 5
*/

Before

#include<cstdio>
#include<cstring>
#include<vector>
#define MAXN (60000+5)
#define max(x,y) ((x)>(y)?(x):(y))
using namespace std;
int f[MAXN][2];
int h[MAXN];
vector<int> son[MAXN];
int p[MAXN];
int n;
void dfs(int);
int main()
{
    int root;
    scanf("%d", &n);

    for(int i = 1; i <= n; i++)
    {
        scanf("%d", &h[i]);
        son[i].clear();
        p[i] = i;
    }

    int srl, srk;

    for(int i = 1; i < n; i++)
    {
        scanf("%d%d", &srl, &srk);
        p[srl] = srk;
        son[srk].push_back(srl);
    }

    scanf("%d%d", &srl, &srk);

    for(int i = 1; i <= n; i++)
    {
        if(p[i] == i)
        {
            root = i;
            break;
        }
    }

    if((!srl) && (!srk))
    {
        dfs(root);
    }

    printf("%d", max(f[root][0], f[root][1]));
    return 0;
}
void dfs(int dqr)
{
    if(dqr > n || dqr < 1)
        return ;

    if(son[dqr].size() == 0)
    {
        f[dqr][0] = 0;
        f[dqr][1] = h[dqr];
        return ;
    }
    else
    {
        f[dqr][1] = h[dqr];
        int max1 = 0;

        for(int i = 0; i < son[dqr].size(); i++)
        {
            dfs(son[dqr][i]);
            max1 = max(f[son[dqr][i]][0], f[son[dqr][i]][1]);
            f[dqr][0] += max1;
            f[dqr][1] += f[son[dqr][i]][0];
        }
    }
}

By 作业写不完文化课爆炸还有点中二的 Cansult