树状DP入门

#include<iostream>
#include<vector>
#include<cmath>
#include<cstdio>
using namespace std;
#define MAXSIZE  6050

vector<int> vec[MAXSIZE];
int weight[MAXSIZE];
int f[MAXSIZE];  //每个节点的父节点
int d[MAXSIZE][2];
int num;

//d[a][0]表示不选择该节点，d[a][1]表示选择该节点
void dfs(int a)  //用来求解d[a][0]和d[a][i]
{
    unsigned int i;
    unsigned int len=vec[a].size();
    d[a][1]=weight[a];
    for(i=0;i<len;i++)
        dfs(vec[a][i]);
    for(i=0;i<len;i++)
    {
        d[a][1]+=d[vec[a][i]][0];
        d[a][0]+=max(d[vec[a][i]][0],d[vec[a][i]][1]);
    }
}
int main()
{
    int i,a,b;
    //freopen("a.txt","r",stdin);
    while(scanf("%d",&num)!=EOF)
    {
        for(i=1;i<=num;i++)
        {
            scanf("%d",&weight[i]);
            vec[i].clear();
            d[i][0]=d[i][1]=0;
            f[i]=-1;//初始化的时候都是没有父节点的
        }
        while(scanf("%d%d",&a,&b),a+b)
        {
            f[a]=b;
            vec[b].push_back(a);
        }
        a=1;
        while(f[a]!=-1)
            a=f[a];
        dfs(a);
        cout<<max(d[a][0],d[a][1])<<endl;

    }
    return 0;
}

<pre name="code" class="cpp">//第二种方法，用结构体来构建无向图
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
#define MAXN 6050
struct node
{
    int v;
    node* next;
}*head[MAXN],tree[MAXN*2];
bool vis[MAXN];
int weight[MAXN];
int ptr,num;
int d[MAXN][2];

void init()
{
    ptr=1;
    memset(vis,false,sizeof(vis));
    memset(head,NULL,sizeof(head));
}

void addEdge(int a,int b)         //该段是模块化编程
{                                 //所有的关于树形DP问题采用无向图方式表示地
    tree[ptr].v=b;                //都是这样构造无向图的
    tree[ptr].next=head[a];       //采用2个一维的数组表示的
    head[a]=&tree[ptr++];
    tree[ptr].v=a;
    tree[ptr].next=head[b];
    head[b]=&tree[ptr++];
}
void bfs(int root)
{
    if(vis[root])   //记忆化搜索，vis[root]为true表示已经求过d[root]
        return ;
    vis[root]=true;
    d[root][1]=weight[root];
    node* p=head[root];
    while(p)
    {
        if(!vis[p->v])  //只有没访问过才求其值
        {
            bfs(p->v);
            d[root][1]+=d[p->v][0];
            d[root][0]+=max(d[p->v][0],d[p->v][1]);
        }
        p=p->next;
    }
}
int main()
{
    int i,a,b;
    freopen("a.txt","r",stdin);
    while(scanf("%d",&num)!=EOF)
    {
        init();
        for(i=1;i<=num;i++)
            scanf("%d",&weight[i]);
        while(scanf("%d%d",&a,&b),a+b)
            addEdge(a,b);
        bfs(1);
        printf("%d\n",max(d[1][0],d[1][1]));
    }



}