节点选择

题意：有一棵 n 个节点的树，树上每个节点都有一个正整数权值。如果一个点被选择了，那么在树上和它相邻的点都不能被选择。求选出的点的权值和最大是多少？

这道题真是闹心了很久啊  然后还是在网上找了一个代码  然后还看了一晚上才看懂的

dfs真是庞大啊

下面看思路吧：

我们用dp[i][0]表示没用i这个点的的最大值  然后用dp[i][1]表示用这个点的最大值然后dp[i][0] += dp[下一个点][1];

dp[i][1] = max(dp[下一个点][1],dp[下一个点][0]);

如果你能想到dfs那么你就成功一半了 不过这个dfs这是让我头疼啊  这个初始化实在是太难了  我们用head[i]数组来存i节点的的第一个子节点，用edge来存每个点的信息edge[i].next表示除了head[i]的第二个子节点 当我们搜索到下一个节点的时候也用同样的方式  先搜下一个点head然后再找next这样一直搜索下去 ，因为这样的搜索可以略过下一个点 也正是符合题意了 不能选相邻的点 搜索结束后我们只需要看dp[1][0]和dp[1][1]哪个更大就可以了

下面看代码：

#include <string.h>
#include <stdio.h>
#include <iostream>
using namespace std;
#define MAX_ 100010
#define max(a,b) ((a>b)?(a):(b))

struct point
{
    int v;
    int next;
}edge[MAX_*2];
int head[MAX_];
int M;
int dp[MAX_][2];
void add(int from,int to)
{
    edge[M].v = to;    //.V是记录这个点是哪个节点
    edge[M].next = head[from];   //把第一个点的next指向下一个点的头
    head[from] = M++;              //
    edge[M].v = from;           //记录第二个点的值
    edge[M].next = head[to];    //第二个点的next指向上一个点的头
    head[to] = M++;
}
void dfs(int x,int pre)   //pre是为了我们不走来时的路的变量
{
    for(int i = head[x];i != -1;i = edge[i].next)
    {

        int v = edge[i].v;
        //printf("x = %d i = %d,v = %d",x,i,v);
        if(pre == v)continue;   //这一步是为了不让我们走来时的路
        dfs(v,x);    //找下一个点 不能与上一个点相同
        dp[x][1] += dp[v][0];
        dp[x][0] += max(dp[v][0],dp[v][1]);
    }
}

int main()
{
    int m,i,n;
    int s,t,c;
    while(~scanf("%d",&n))
    {
        M = 0;
        memset(head,-1,sizeof(head));
        memset(dp,0,sizeof(dp));
        for(i = 1;i <= n;i++)
        {
            scanf("%d",&dp[i][1]);
        }
        for(i = 1;i < n;i++)
        {
            scanf("%d%d",&s,&t);
            add(s,t);
        }
        dfs(1,-1);
        int tmp = max(dp[1][0],dp[1][1]);
        printf("%d\n",tmp);
    }
    return 0;
}